Go back to index | PHP CodeBrowser

phpseclib/Math/BigInteger.php
  1.    1  <?php
  2.    2 
  3.    3 /**
  4.    4  * Pure-PHP arbitrary precision integer arithmetic library.
  5.    5  *
  6.    6  * Supports base-2, base-10, base-16, and base-256 numbers.  Uses the GMP or BCMath extensions, if available,
  7.    7  * and an internal implementation, otherwise.
  8.    8  *
  9.    9  * PHP versions 4 and 5
  10.   10  *
  11.   11  * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
  12.   12  * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
  13.   13  *
  14.   14  * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
  15.   15  * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction.  Because the largest possible
  16.   16  * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
  17.   17  * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
  18.   18  * used.  As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
  19.   19  * which only supports integers.  Although this fact will slow this library down, the fact that such a high
  20.   20  * base is being used should more than compensate.
  21.   21  *
  22.   22  * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format.  ie.
  23.   23  * (new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
  24.   24  *
  25.   25  * Useful resources are as follows:
  26.   26  *
  27.   27  *  - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
  28.   28  *  - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
  29.   29  *  - Java's BigInteger classes.  See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
  30.   30  *
  31.   31  * Here's an example of how to use this library:
  32.   32  * <code>
  33.   33  * <?php
  34.   34  *    include 'Math/BigInteger.php';
  35.   35  *
  36.   36  *    $a = new Math_BigInteger(2);
  37.   37  *    $b = new Math_BigInteger(3);
  38.   38  *
  39.   39  *    $c = $a->add($b);
  40.   40  *
  41.   41  *    echo $c->toString(); // outputs 5
  42.   42  * ?>
  43.   43  * </code>
  44.   44  *
  45.   45  * LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy
  46.   46  * of this software and associated documentation files (the "Software"), to deal
  47.   47  * in the Software without restriction, including without limitation the rights
  48.   48  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  49.   49  * copies of the Software, and to permit persons to whom the Software is
  50.   50  * furnished to do so, subject to the following conditions:
  51.   51  *
  52.   52  * The above copyright notice and this permission notice shall be included in
  53.   53  * all copies or substantial portions of the Software.
  54.   54  *
  55.   55  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  56.   56  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  57.   57  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  58.   58  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  59.   59  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  60.   60  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  61.   61  * THE SOFTWARE.
  62.   62  *
  63.   63  * @category  Math
  64.   64  * @package   Math_BigInteger
  65.   65  * @author    Jim Wigginton <terrafrost@php.net>
  66.   66  * @copyright 2006 Jim Wigginton
  67.   67  * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  68.   68  * @link      http://pear.php.net/package/Math_BigInteger
  69.   69  */
  70.   70 
  71.   71 /**#@+
  72.   72  * Reduction constants
  73.   73  *
  74.   74  * @access private
  75.   75  * @see self::_reduce()
  76.   76  */
  77.   77 /**
  78.   78  * @see self::_montgomery()
  79.   79  * @see self::_prepMontgomery()
  80.   80  */
  81.   81 define('MATH_BIGINTEGER_MONTGOMERY'0);
  82.   82 /**
  83.   83  * @see self::_barrett()
  84.   84  */
  85.   85 define('MATH_BIGINTEGER_BARRETT'1);
  86.   86 /**
  87.   87  * @see self::_mod2()
  88.   88  */
  89.   89 define('MATH_BIGINTEGER_POWEROF2'2);
  90.   90 /**
  91.   91  * @see self::_remainder()
  92.   92  */
  93.   93 define('MATH_BIGINTEGER_CLASSIC'3);
  94.   94 /**
  95.   95  * @see self::__clone()
  96.   96  */
  97.   97 define('MATH_BIGINTEGER_NONE'4);
  98.   98 /**#@-*/
  99.   99 
  100.  100 /**#@+
  101.  101  * Array constants
  102.  102  *
  103.  103  * Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and
  104.  104  * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
  105.  105  *
  106.  106  * @access private
  107.  107  */
  108.  108 /**
  109.  109  * $result[MATH_BIGINTEGER_VALUE] contains the value.
  110.  110  */
  111.  111 define('MATH_BIGINTEGER_VALUE'0);
  112.  112 /**
  113.  113  * $result[MATH_BIGINTEGER_SIGN] contains the sign.
  114.  114  */
  115.  115 define('MATH_BIGINTEGER_SIGN'1);
  116.  116 /**#@-*/
  117.  117 
  118.  118 /**#@+
  119.  119  * @access private
  120.  120  * @see self::_montgomery()
  121.  121  * @see self::_barrett()
  122.  122  */
  123.  123 /**
  124.  124  * Cache constants
  125.  125  *
  126.  126  * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
  127.  127  */
  128.  128 define('MATH_BIGINTEGER_VARIABLE'0);
  129.  129 /**
  130.  130  * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
  131.  131  */
  132.  132 define('MATH_BIGINTEGER_DATA'1);
  133.  133 /**#@-*/
  134.  134 
  135.  135 /**#@+
  136.  136  * Mode constants.
  137.  137  *
  138.  138  * @access private
  139.  139  * @see self::Math_BigInteger()
  140.  140  */
  141.  141 /**
  142.  142  * To use the pure-PHP implementation
  143.  143  */
  144.  144 define('MATH_BIGINTEGER_MODE_INTERNAL'1);
  145.  145 /**
  146.  146  * To use the BCMath library
  147.  147  *
  148.  148  * (if enabled; otherwise, the internal implementation will be used)
  149.  149  */
  150.  150 define('MATH_BIGINTEGER_MODE_BCMATH'2);
  151.  151 /**
  152.  152  * To use the GMP library
  153.  153  *
  154.  154  * (if present; otherwise, either the BCMath or the internal implementation will be used)
  155.  155  */
  156.  156 define('MATH_BIGINTEGER_MODE_GMP'3);
  157.  157 /**#@-*/
  158.  158 
  159.  159 /**
  160.  160  * Karatsuba Cutoff
  161.  161  *
  162.  162  * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
  163.  163  *
  164.  164  * @access private
  165.  165  */
  166.  166 define('MATH_BIGINTEGER_KARATSUBA_CUTOFF'25);
  167.  167 
  168.  168 /**
  169.  169  * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
  170.  170  * numbers.
  171.  171  *
  172.  172  * @package Math_BigInteger
  173.  173  * @author  Jim Wigginton <terrafrost@php.net>
  174.  174  * @access  public
  175.  175  */
  176.  176 class Math_BigInteger
  177.  177 {
  178.  178     /**
  179.  179      * Holds the BigInteger's value.
  180.  180      *
  181.  181      * @var array
  182.  182      * @access private
  183.  183      */
  184.  184     var $value;
  185.  185 
  186.  186     /**
  187.  187      * Holds the BigInteger's magnitude.
  188.  188      *
  189.  189      * @var bool
  190.  190      * @access private
  191.  191      */
  192.  192     var $is_negative false;
  193.  193 
  194.  194     /**
  195.  195      * Precision
  196.  196      *
  197.  197      * @see self::setPrecision()
  198.  198      * @access private
  199.  199      */
  200.  200     var $precision = -1;
  201.  201 
  202.  202     /**
  203.  203      * Precision Bitmask
  204.  204      *
  205.  205      * @see self::setPrecision()
  206.  206      * @access private
  207.  207      */
  208.  208     var $bitmask false;
  209.  209 
  210.  210     /**
  211.  211      * Mode independent value used for serialization.
  212.  212      *
  213.  213      * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
  214.  214      * a variable that'll be serializable regardless of whether or not extensions are being used.  Unlike $this->value,
  215.  215      * however, $this->hex is only calculated when $this->__sleep() is called.
  216.  216      *
  217.  217      * @see self::__sleep()
  218.  218      * @see self::__wakeup()
  219.  219      * @var string
  220.  220      * @access private
  221.  221      */
  222.  222     var $hex;
  223.  223 
  224.  224     /**
  225.  225      * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
  226.  226      *
  227.  227      * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
  228.  228      * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
  229.  229      *
  230.  230      * Here's an example:
  231.  231      * <code>
  232.  232      * <?php
  233.  233      *    include 'Math/BigInteger.php';
  234.  234      *
  235.  235      *    $a = new Math_BigInteger('0x32', 16); // 50 in base-16
  236.  236      *
  237.  237      *    echo $a->toString(); // outputs 50
  238.  238      * ?>
  239.  239      * </code>
  240.  240      *
  241.  241      * @param $x base-10 number or base-$base number if $base set.
  242.  242      * @param int $base
  243.  243      * @return Math_BigInteger
  244.  244      * @access public
  245.  245      */
  246.  246     function __construct($x 0$base 10)
  247.  247     {
  248.  248         if (!defined('MATH_BIGINTEGER_MODE')) {
  249.  249             switch (true) {
  250.  250                 case extension_loaded('gmp'):
  251.  251                     define('MATH_BIGINTEGER_MODE'MATH_BIGINTEGER_MODE_GMP);
  252.  252                     break;
  253.  253                 case extension_loaded('bcmath'):
  254.  254                     define('MATH_BIGINTEGER_MODE'MATH_BIGINTEGER_MODE_BCMATH);
  255.  255                     break;
  256.  256                 default:
  257.  257                     define('MATH_BIGINTEGER_MODE'MATH_BIGINTEGER_MODE_INTERNAL);
  258.  258             }
  259.  259         }
  260.  260 
  261.  261         if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
  262.  262             // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
  263.  263             ob_start();
  264.  264             @phpinfo();
  265.  265             $content ob_get_contents();
  266.  266             ob_end_clean();
  267.  267 
  268.  268             preg_match_all('#OpenSSL (Header|Library) Version(.*)#im'$content$matches);
  269.  269 
  270.  270             $versions = array();
  271.  271             if (!empty($matches[1])) {
  272.  272                 for ($i 0$i count($matches[1]); $i++) {
  273.  273                     $fullVersion trim(str_replace('=>'''strip_tags($matches[2][$i])));
  274.  274 
  275.  275                     // Remove letter part in OpenSSL version
  276.  276                     if (!preg_match('/(\d+\.\d+\.\d+)/i'$fullVersion$m)) {
  277.  277                         $versions[$matches[1][$i]] = $fullVersion;
  278.  278                     } else {
  279.  279                         $versions[$matches[1][$i]] = $m[0];
  280.  280                     }
  281.  281                 }
  282.  282             }
  283.  283 
  284.  284             // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
  285.  285             switch (true) {
  286.  286                 case !isset($versions['Header']):
  287.  287                 case !isset($versions['Library']):
  288.  288                 case $versions['Header'] == $versions['Library']:
  289.  289                 case version_compare($versions['Header'], '1.0.0') >= && version_compare($versions['Library'], '1.0.0') >= 0:
  290.  290                     define('MATH_BIGINTEGER_OPENSSL_ENABLED'true);
  291.  291                     break;
  292.  292                 default:
  293.  293                     define('MATH_BIGINTEGER_OPENSSL_DISABLE'true);
  294.  294             }
  295.  295         }
  296.  296 
  297.  297         if (!defined('PHP_INT_SIZE')) {
  298.  298             define('PHP_INT_SIZE'4);
  299.  299         }
  300.  300 
  301.  301         if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
  302.  302             switch (PHP_INT_SIZE) {
  303.  303                 case 8// use 64-bit integers if int size is 8 bytes
  304.  304                     define('MATH_BIGINTEGER_BASE',       31);
  305.  305                     define('MATH_BIGINTEGER_BASE_FULL',  0x80000000);
  306.  306                     define('MATH_BIGINTEGER_MAX_DIGIT',  0x7FFFFFFF);
  307.  307                     define('MATH_BIGINTEGER_MSB',        0x40000000);
  308.  308                     // 10**9 is the closest we can get to 2**31 without passing it
  309.  309                     define('MATH_BIGINTEGER_MAX10',      1000000000);
  310.  310                     define('MATH_BIGINTEGER_MAX10_LEN',  9);
  311.  311                     // the largest digit that may be used in addition / subtraction
  312.  312                     define('MATH_BIGINTEGER_MAX_DIGIT2'pow(262));
  313.  313                     break;
  314.  314                 //case 4: // use 64-bit floats if int size is 4 bytes
  315.  315                 default:
  316.  316                     define('MATH_BIGINTEGER_BASE',       26);
  317.  317                     define('MATH_BIGINTEGER_BASE_FULL',  0x4000000);
  318.  318                     define('MATH_BIGINTEGER_MAX_DIGIT',  0x3FFFFFF);
  319.  319                     define('MATH_BIGINTEGER_MSB',        0x2000000);
  320.  320                     // 10**7 is the closest to 2**26 without passing it
  321.  321                     define('MATH_BIGINTEGER_MAX10',      10000000);
  322.  322                     define('MATH_BIGINTEGER_MAX10_LEN',  7);
  323.  323                     // the largest digit that may be used in addition / subtraction
  324.  324                     // we do pow(2, 52) instead of using 4503599627370496 directly because some
  325.  325                     // PHP installations will truncate 4503599627370496.
  326.  326                     define('MATH_BIGINTEGER_MAX_DIGIT2'pow(252));
  327.  327             }
  328.  328         }
  329.  329 
  330.  330         switch (MATH_BIGINTEGER_MODE) {
  331.  331             case MATH_BIGINTEGER_MODE_GMP:
  332.  332                 switch (true) {
  333.  333                     case is_resource($x) && get_resource_type($x) == 'GMP integer':
  334.  334                     // PHP 5.6 switched GMP from using resources to objects
  335.  335                     case is_object($x) && get_class($x) == 'GMP':
  336.  336                         $this->value $x;
  337.  337                         return;
  338.  338                 }
  339.  339                 $this->value gmp_init(0);
  340.  340                 break;
  341.  341             case MATH_BIGINTEGER_MODE_BCMATH:
  342.  342                 $this->value '0';
  343.  343                 break;
  344.  344             default:
  345.  345                 $this->value = array();
  346.  346         }
  347.  347 
  348.  348         // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
  349.  349         // '0' is the only value like this per http://php.net/empty
  350.  350         if (empty($x) && (abs($base) != 256 || $x !== '0')) {
  351.  351             return;
  352.  352         }
  353.  353 
  354.  354         switch ($base) {
  355.  355             case -256:
  356.  356                 if (ord($x[0]) & 0x80) {
  357.  357                     $x = ~$x;
  358.  358                     $this->is_negative true;
  359.  359                 }
  360.  360             case 256:
  361.  361                 switch (MATH_BIGINTEGER_MODE) {
  362.  362                     case MATH_BIGINTEGER_MODE_GMP:
  363.  363                         $this->value function_exists('gmp_import') ?
  364.  364                             gmp_import($x) :
  365.  365                             gmp_init('0x' bin2hex($x));
  366.  366                         if ($this->is_negative) {
  367.  367                             $this->value gmp_neg($this->value);
  368.  368                         }
  369.  369                         break;
  370.  370                     case MATH_BIGINTEGER_MODE_BCMATH:
  371.  371                         // round $len to the nearest 4 (thanks, DavidMJ!)
  372.  372                         $len = (strlen($x) + 3) & 0xFFFFFFFC;
  373.  373 
  374.  374                         $x str_pad($x$lenchr(0), STR_PAD_LEFT);
  375.  375 
  376.  376                         for ($i 0$i $len$i+= 4) {
  377.  377                             $this->value bcmul($this->value'4294967296'0); // 4294967296 == 2**32
  378.  378                             $this->value bcadd($this->value0x1000000 ord($x[$i]) + ((ord($x[$i 1]) << 16) | (ord($x[$i 2]) << 8) | ord($x[$i 3])), 0);
  379.  379                         }
  380.  380 
  381.  381                         if ($this->is_negative) {
  382.  382                             $this->value '-' $this->value;
  383.  383                         }
  384.  384 
  385.  385                         break;
  386.  386                     // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
  387.  387                     default:
  388.  388                         while (strlen($x)) {
  389.  389                             $this->value[] = $this->_bytes2int($this->_base256_rshift($xMATH_BIGINTEGER_BASE));
  390.  390                         }
  391.  391                 }
  392.  392 
  393.  393                 if ($this->is_negative) {
  394.  394                     if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
  395.  395                         $this->is_negative false;
  396.  396                     }
  397.  397                     $temp $this->add(new Math_BigInteger('-1'));
  398.  398                     $this->value $temp->value;
  399.  399                 }
  400.  400                 break;
  401.  401             case 16:
  402.  402             case -16:
  403.  403                 if ($base && $x[0] == '-') {
  404.  404                     $this->is_negative true;
  405.  405                     $x substr($x1);
  406.  406                 }
  407.  407 
  408.  408                 $x preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#''$1'$x);
  409.  409 
  410.  410                 $is_negative false;
  411.  411                 if ($base && hexdec($x[0]) >= 8) {
  412.  412                     $this->is_negative $is_negative true;
  413.  413                     $x bin2hex(~pack('H*'$x));
  414.  414                 }
  415.  415 
  416.  416                 switch (MATH_BIGINTEGER_MODE) {
  417.  417                     case MATH_BIGINTEGER_MODE_GMP:
  418.  418                         $temp $this->is_negative '-0x' $x '0x' $x;
  419.  419                         $this->value gmp_init($temp);
  420.  420                         $this->is_negative false;
  421.  421                         break;
  422.  422                     case MATH_BIGINTEGER_MODE_BCMATH:
  423.  423                         $x = (strlen($x) & 1) ? '0' $x $x;
  424.  424                         $temp = new Math_BigInteger(pack('H*'$x), 256);
  425.  425                         $this->value $this->is_negative '-' $temp->value $temp->value;
  426.  426                         $this->is_negative false;
  427.  427                         break;
  428.  428                     default:
  429.  429                         $x = (strlen($x) & 1) ? '0' $x $x;
  430.  430                         $temp = new Math_BigInteger(pack('H*'$x), 256);
  431.  431                         $this->value $temp->value;
  432.  432                 }
  433.  433 
  434.  434                 if ($is_negative) {
  435.  435                     $temp $this->add(new Math_BigInteger('-1'));
  436.  436                     $this->value $temp->value;
  437.  437                 }
  438.  438                 break;
  439.  439             case 10:
  440.  440             case -10:
  441.  441                 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
  442.  442                 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
  443.  443                 // [^-0-9].*: find any non-numeric characters and then any characters that follow that
  444.  444                 $x preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#'''$x);
  445.  445 
  446.  446                 switch (MATH_BIGINTEGER_MODE) {
  447.  447                     case MATH_BIGINTEGER_MODE_GMP:
  448.  448                         $this->value gmp_init($x);
  449.  449                         break;
  450.  450                     case MATH_BIGINTEGER_MODE_BCMATH:
  451.  451                         // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
  452.  452                         // results then doing it on '-1' does (modInverse does $x[0])
  453.  453                         $this->value $x === '-' '0' : (string) $x;
  454.  454                         break;
  455.  455                     default:
  456.  456                         $temp = new Math_BigInteger();
  457.  457 
  458.  458                         $multiplier = new Math_BigInteger();
  459.  459                         $multiplier->value = array(MATH_BIGINTEGER_MAX10);
  460.  460 
  461.  461                         if ($x[0] == '-') {
  462.  462                             $this->is_negative true;
  463.  463                             $x substr($x1);
  464.  464                         }
  465.  465 
  466.  466                         $x str_pad($xstrlen($x) + ((MATH_BIGINTEGER_MAX10_LEN 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN0STR_PAD_LEFT);
  467.  467                         while (strlen($x)) {
  468.  468                             $temp $temp->multiply($multiplier);
  469.  469                             $temp $temp->add(new Math_BigInteger($this->_int2bytes(substr($x0MATH_BIGINTEGER_MAX10_LEN)), 256));
  470.  470                             $x substr($xMATH_BIGINTEGER_MAX10_LEN);
  471.  471                         }
  472.  472 
  473.  473                         $this->value $temp->value;
  474.  474                 }
  475.  475                 break;
  476.  476             case 2// base-2 support originally implemented by Lluis Pamies - thanks!
  477.  477             case -2:
  478.  478                 if ($base && $x[0] == '-') {
  479.  479                     $this->is_negative true;
  480.  480                     $x substr($x1);
  481.  481                 }
  482.  482 
  483.  483                 $x preg_replace('#^([01]*).*#''$1'$x);
  484.  484                 $x str_pad($xstrlen($x) + (strlen($x)) % 40STR_PAD_LEFT);
  485.  485 
  486.  486                 $str '0x';
  487.  487                 while (strlen($x)) {
  488.  488                     $part substr($x04);
  489.  489                     $str.= dechex(bindec($part));
  490.  490                     $x substr($x4);
  491.  491                 }
  492.  492 
  493.  493                 if ($this->is_negative) {
  494.  494                     $str '-' $str;
  495.  495                 }
  496.  496 
  497.  497                 $temp = new Math_BigInteger($str$base); // ie. either -16 or +16
  498.  498                 $this->value $temp->value;
  499.  499                 $this->is_negative $temp->is_negative;
  500.  500 
  501.  501                 break;
  502.  502             default:
  503.  503                 // base not supported, so we'll let $this == 0
  504.  504         }
  505.  505     }
  506.  506 
  507.  507     /**
  508.  508      * PHP4 compatible Default Constructor.
  509.  509      *
  510.  510      * @see self::__construct()
  511.  511      * @param $x base-10 number or base-$base number if $base set.
  512.  512      * @param int $base
  513.  513      * @access public
  514.  514      */
  515.  515     function Math_BigInteger($x 0$base 10)
  516.  516     {
  517.  517         $this->__construct($x$base);
  518.  518     }
  519.  519 
  520.  520     /**
  521.  521      * Converts a BigInteger to a byte string (eg. base-256).
  522.  522      *
  523.  523      * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  524.  524      * saved as two's compliment.
  525.  525      *
  526.  526      * Here's an example:
  527.  527      * <code>
  528.  528      * <?php
  529.  529      *    include 'Math/BigInteger.php';
  530.  530      *
  531.  531      *    $a = new Math_BigInteger('65');
  532.  532      *
  533.  533      *    echo $a->toBytes(); // outputs chr(65)
  534.  534      * ?>
  535.  535      * </code>
  536.  536      *
  537.  537      * @param bool $twos_compliment
  538.  538      * @return string
  539.  539      * @access public
  540.  540      * @internal Converts a base-2**26 number to base-2**8
  541.  541      */
  542.  542     function toBytes($twos_compliment false)
  543.  543     {
  544.  544         if ($twos_compliment) {
  545.  545             $comparison $this->compare(new Math_BigInteger());
  546.  546             if ($comparison == 0) {
  547.  547                 return $this->precision str_repeat(chr(0), ($this->precision 1) >> 3) : '';
  548.  548             }
  549.  549 
  550.  550             $temp $comparison $this->add(new Math_BigInteger(1)) : $this->copy();
  551.  551             $bytes $temp->toBytes();
  552.  552 
  553.  553             if (empty($bytes)) { // eg. if the number we're trying to convert is -1
  554.  554                 $bytes chr(0);
  555.  555             }
  556.  556 
  557.  557             if (ord($bytes[0]) & 0x80) {
  558.  558                 $bytes chr(0) . $bytes;
  559.  559             }
  560.  560 
  561.  561             return $comparison ? ~$bytes $bytes;
  562.  562         }
  563.  563 
  564.  564         switch (MATH_BIGINTEGER_MODE) {
  565.  565             case MATH_BIGINTEGER_MODE_GMP:
  566.  566                 if (gmp_cmp($this->valuegmp_init(0)) == 0) {
  567.  567                     return $this->precision str_repeat(chr(0), ($this->precision 1) >> 3) : '';
  568.  568                 }
  569.  569 
  570.  570                 if (function_exists('gmp_export')) {
  571.  571                     $temp gmp_export($this->value);
  572.  572                 } else {
  573.  573                     $temp gmp_strval(gmp_abs($this->value), 16);
  574.  574                     $temp = (strlen($temp) & 1) ? '0' $temp $temp;
  575.  575                     $temp pack('H*'$temp);
  576.  576                 }
  577.  577 
  578.  578                 return $this->precision ?
  579.  579                     substr(str_pad($temp$this->precision >> 3chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
  580.  580                     ltrim($tempchr(0));
  581.  581             case MATH_BIGINTEGER_MODE_BCMATH:
  582.  582                 if ($this->value === '0') {
  583.  583                     return $this->precision str_repeat(chr(0), ($this->precision 1) >> 3) : '';
  584.  584                 }
  585.  585 
  586.  586                 $value '';
  587.  587                 $current $this->value;
  588.  588 
  589.  589                 if ($current[0] == '-') {
  590.  590                     $current substr($current1);
  591.  591                 }
  592.  592 
  593.  593                 while (bccomp($current'0'0) > 0) {
  594.  594                     $temp bcmod($current'16777216');
  595.  595                     $value chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
  596.  596                     $current bcdiv($current'16777216'0);
  597.  597                 }
  598.  598 
  599.  599                 return $this->precision ?
  600.  600                     substr(str_pad($value$this->precision >> 3chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
  601.  601                     ltrim($valuechr(0));
  602.  602         }
  603.  603 
  604.  604         if (!count($this->value)) {
  605.  605             return $this->precision str_repeat(chr(0), ($this->precision 1) >> 3) : '';
  606.  606         }
  607.  607         $result $this->_int2bytes($this->value[count($this->value) - 1]);
  608.  608 
  609.  609         $temp $this->copy();
  610.  610 
  611.  611         for ($i count($temp->value) - 2$i >= 0; --$i) {
  612.  612             $temp->_base256_lshift($resultMATH_BIGINTEGER_BASE);
  613.  613             $result $result str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
  614.  614         }
  615.  615 
  616.  616         return $this->precision ?
  617.  617             str_pad(substr($result, -(($this->precision 7) >> 3)), ($this->precision 7) >> 3chr(0), STR_PAD_LEFT) :
  618.  618             $result;
  619.  619     }
  620.  620 
  621.  621     /**
  622.  622      * Converts a BigInteger to a hex string (eg. base-16)).
  623.  623      *
  624.  624      * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  625.  625      * saved as two's compliment.
  626.  626      *
  627.  627      * Here's an example:
  628.  628      * <code>
  629.  629      * <?php
  630.  630      *    include 'Math/BigInteger.php';
  631.  631      *
  632.  632      *    $a = new Math_BigInteger('65');
  633.  633      *
  634.  634      *    echo $a->toHex(); // outputs '41'
  635.  635      * ?>
  636.  636      * </code>
  637.  637      *
  638.  638      * @param bool $twos_compliment
  639.  639      * @return string
  640.  640      * @access public
  641.  641      * @internal Converts a base-2**26 number to base-2**8
  642.  642      */
  643.  643     function toHex($twos_compliment false)
  644.  644     {
  645.  645         return bin2hex($this->toBytes($twos_compliment));
  646.  646     }
  647.  647 
  648.  648     /**
  649.  649      * Converts a BigInteger to a bit string (eg. base-2).
  650.  650      *
  651.  651      * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  652.  652      * saved as two's compliment.
  653.  653      *
  654.  654      * Here's an example:
  655.  655      * <code>
  656.  656      * <?php
  657.  657      *    include 'Math/BigInteger.php';
  658.  658      *
  659.  659      *    $a = new Math_BigInteger('65');
  660.  660      *
  661.  661      *    echo $a->toBits(); // outputs '1000001'
  662.  662      * ?>
  663.  663      * </code>
  664.  664      *
  665.  665      * @param bool $twos_compliment
  666.  666      * @return string
  667.  667      * @access public
  668.  668      * @internal Converts a base-2**26 number to base-2**2
  669.  669      */
  670.  670     function toBits($twos_compliment false)
  671.  671     {
  672.  672         $hex $this->toHex($twos_compliment);
  673.  673         $bits '';
  674.  674         for ($i strlen($hex) - 8$start strlen($hex) & 7$i >= $start$i-=8) {
  675.  675             $bits str_pad(decbin(hexdec(substr($hex$i8))), 32'0'STR_PAD_LEFT) . $bits;
  676.  676         }
  677.  677         if ($start) { // hexdec('') == 0
  678.  678             $bits str_pad(decbin(hexdec(substr($hex0$start))), 8'0'STR_PAD_LEFT) . $bits;
  679.  679         }
  680.  680         $result $this->precision substr($bits, -$this->precision) : ltrim($bits'0');
  681.  681 
  682.  682         if ($twos_compliment && $this->compare(new Math_BigInteger()) > && $this->precision <= 0) {
  683.  683             return '0' $result;
  684.  684         }
  685.  685 
  686.  686         return $result;
  687.  687     }
  688.  688 
  689.  689     /**
  690.  690      * Converts a BigInteger to a base-10 number.
  691.  691      *
  692.  692      * Here's an example:
  693.  693      * <code>
  694.  694      * <?php
  695.  695      *    include 'Math/BigInteger.php';
  696.  696      *
  697.  697      *    $a = new Math_BigInteger('50');
  698.  698      *
  699.  699      *    echo $a->toString(); // outputs 50
  700.  700      * ?>
  701.  701      * </code>
  702.  702      *
  703.  703      * @return string
  704.  704      * @access public
  705.  705      * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
  706.  706      */
  707.  707     function toString()
  708.  708     {
  709.  709         switch (MATH_BIGINTEGER_MODE) {
  710.  710             case MATH_BIGINTEGER_MODE_GMP:
  711.  711                 return gmp_strval($this->value);
  712.  712             case MATH_BIGINTEGER_MODE_BCMATH:
  713.  713                 if ($this->value === '0') {
  714.  714                     return '0';
  715.  715                 }
  716.  716 
  717.  717                 return ltrim($this->value'0');
  718.  718         }
  719.  719 
  720.  720         if (!count($this->value)) {
  721.  721             return '0';
  722.  722         }
  723.  723 
  724.  724         $temp $this->copy();
  725.  725         $temp->is_negative false;
  726.  726 
  727.  727         $divisor = new Math_BigInteger();
  728.  728         $divisor->value = array(MATH_BIGINTEGER_MAX10);
  729.  729         $result '';
  730.  730         while (count($temp->value)) {
  731.  731             list($temp$mod) = $temp->divide($divisor);
  732.  732             $result str_pad(isset($mod->value[0]) ? $mod->value[0] : ''MATH_BIGINTEGER_MAX10_LEN'0'STR_PAD_LEFT) . $result;
  733.  733         }
  734.  734         $result ltrim($result'0');
  735.  735         if (empty($result)) {
  736.  736             $result '0';
  737.  737         }
  738.  738 
  739.  739         if ($this->is_negative) {
  740.  740             $result '-' $result;
  741.  741         }
  742.  742 
  743.  743         return $result;
  744.  744     }
  745.  745 
  746.  746     /**
  747.  747      * Copy an object
  748.  748      *
  749.  749      * PHP5 passes objects by reference while PHP4 passes by value.  As such, we need a function to guarantee
  750.  750      * that all objects are passed by value, when appropriate.  More information can be found here:
  751.  751      *
  752.  752      * {@link http://php.net/language.oop5.basic#51624}
  753.  753      *
  754.  754      * @access public
  755.  755      * @see self::__clone()
  756.  756      * @return Math_BigInteger
  757.  757      */
  758.  758     function copy()
  759.  759     {
  760.  760         $temp = new Math_BigInteger();
  761.  761         $temp->value $this->value;
  762.  762         $temp->is_negative $this->is_negative;
  763.  763         $temp->precision $this->precision;
  764.  764         $temp->bitmask $this->bitmask;
  765.  765         return $temp;
  766.  766     }
  767.  767 
  768.  768     /**
  769.  769      *  __toString() magic method
  770.  770      *
  771.  771      * Will be called, automatically, if you're supporting just PHP5.  If you're supporting PHP4, you'll need to call
  772.  772      * toString().
  773.  773      *
  774.  774      * @access public
  775.  775      * @internal Implemented per a suggestion by Techie-Michael - thanks!
  776.  776      */
  777.  777     function __toString()
  778.  778     {
  779.  779         return $this->toString();
  780.  780     }
  781.  781 
  782.  782     /**
  783.  783      * __clone() magic method
  784.  784      *
  785.  785      * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
  786.  786      * directly in PHP5.  You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5
  787.  787      * only syntax of $y = clone $x.  As such, if you're trying to write an application that works on both PHP4 and PHP5,
  788.  788      * call Math_BigInteger::copy(), instead.
  789.  789      *
  790.  790      * @access public
  791.  791      * @see self::copy()
  792.  792      * @return Math_BigInteger
  793.  793      */
  794.  794     function __clone()
  795.  795     {
  796.  796         return $this->copy();
  797.  797     }
  798.  798 
  799.  799     /**
  800.  800      *  __sleep() magic method
  801.  801      *
  802.  802      * Will be called, automatically, when serialize() is called on a Math_BigInteger object.
  803.  803      *
  804.  804      * @see self::__wakeup()
  805.  805      * @access public
  806.  806      */
  807.  807     function __sleep()
  808.  808     {
  809.  809         $this->hex $this->toHex(true);
  810.  810         $vars = array('hex');
  811.  811         if ($this->precision 0) {
  812.  812             $vars[] = 'precision';
  813.  813         }
  814.  814         return $vars;
  815.  815     }
  816.  816 
  817.  817     /**
  818.  818      *  __wakeup() magic method
  819.  819      *
  820.  820      * Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
  821.  821      *
  822.  822      * @see self::__sleep()
  823.  823      * @access public
  824.  824      */
  825.  825     function __wakeup()
  826.  826     {
  827.  827         $temp = new Math_BigInteger($this->hex, -16);
  828.  828         $this->value $temp->value;
  829.  829         $this->is_negative $temp->is_negative;
  830.  830         if ($this->precision 0) {
  831.  831             // recalculate $this->bitmask
  832.  832             $this->setPrecision($this->precision);
  833.  833         }
  834.  834     }
  835.  835 
  836.  836     /**
  837.  837      *  __debugInfo() magic method
  838.  838      *
  839.  839      * Will be called, automatically, when print_r() or var_dump() are called
  840.  840      *
  841.  841      * @access public
  842.  842      */
  843.  843     function __debugInfo()
  844.  844     {
  845.  845         $opts = array();
  846.  846         switch (MATH_BIGINTEGER_MODE) {
  847.  847             case MATH_BIGINTEGER_MODE_GMP:
  848.  848                 $engine 'gmp';
  849.  849                 break;
  850.  850             case MATH_BIGINTEGER_MODE_BCMATH:
  851.  851                 $engine 'bcmath';
  852.  852                 break;
  853.  853             case MATH_BIGINTEGER_MODE_INTERNAL:
  854.  854                 $engine 'internal';
  855.  855                 $opts[] = PHP_INT_SIZE == '64-bit' '32-bit';
  856.  856         }
  857.  857         if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
  858.  858             $opts[] = 'OpenSSL';
  859.  859         }
  860.  860         if (!empty($opts)) {
  861.  861             $engine.= ' (' implode($opts', ') . ')';
  862.  862         }
  863.  863         return array(
  864.  864             'value' => '0x' $this->toHex(true),
  865.  865             'engine' => $engine
  866.  866         );
  867.  867     }
  868.  868 
  869.  869     /**
  870.  870      * Adds two BigIntegers.
  871.  871      *
  872.  872      * Here's an example:
  873.  873      * <code>
  874.  874      * <?php
  875.  875      *    include 'Math/BigInteger.php';
  876.  876      *
  877.  877      *    $a = new Math_BigInteger('10');
  878.  878      *    $b = new Math_BigInteger('20');
  879.  879      *
  880.  880      *    $c = $a->add($b);
  881.  881      *
  882.  882      *    echo $c->toString(); // outputs 30
  883.  883      * ?>
  884.  884      * </code>
  885.  885      *
  886.  886      * @param Math_BigInteger $y
  887.  887      * @return Math_BigInteger
  888.  888      * @access public
  889.  889      * @internal Performs base-2**52 addition
  890.  890      */
  891.  891     function add($y)
  892.  892     {
  893.  893         switch (MATH_BIGINTEGER_MODE) {
  894.  894             case MATH_BIGINTEGER_MODE_GMP:
  895.  895                 $temp = new Math_BigInteger();
  896.  896                 $temp->value gmp_add($this->value$y->value);
  897.  897 
  898.  898                 return $this->_normalize($temp);
  899.  899             case MATH_BIGINTEGER_MODE_BCMATH:
  900.  900                 $temp = new Math_BigInteger();
  901.  901                 $temp->value bcadd($this->value$y->value0);
  902.  902 
  903.  903                 return $this->_normalize($temp);
  904.  904         }
  905.  905 
  906.  906         $temp $this->_add($this->value$this->is_negative$y->value$y->is_negative);
  907.  907 
  908.  908         $result = new Math_BigInteger();
  909.  909         $result->value $temp[MATH_BIGINTEGER_VALUE];
  910.  910         $result->is_negative $temp[MATH_BIGINTEGER_SIGN];
  911.  911 
  912.  912         return $this->_normalize($result);
  913.  913     }
  914.  914 
  915.  915     /**
  916.  916      * Performs addition.
  917.  917      *
  918.  918      * @param array $x_value
  919.  919      * @param bool $x_negative
  920.  920      * @param array $y_value
  921.  921      * @param bool $y_negative
  922.  922      * @return array
  923.  923      * @access private
  924.  924      */
  925.  925     function _add($x_value$x_negative$y_value$y_negative)
  926.  926     {
  927.  927         $x_size count($x_value);
  928.  928         $y_size count($y_value);
  929.  929 
  930.  930         if ($x_size == 0) {
  931.  931             return array(
  932.  932                 MATH_BIGINTEGER_VALUE => $y_value,
  933.  933                 MATH_BIGINTEGER_SIGN => $y_negative
  934.  934             );
  935.  935         } elseif ($y_size == 0) {
  936.  936             return array(
  937.  937                 MATH_BIGINTEGER_VALUE => $x_value,
  938.  938                 MATH_BIGINTEGER_SIGN => $x_negative
  939.  939             );
  940.  940         }
  941.  941 
  942.  942         // subtract, if appropriate
  943.  943         if ($x_negative != $y_negative) {
  944.  944             if ($x_value == $y_value) {
  945.  945                 return array(
  946.  946                     MATH_BIGINTEGER_VALUE => array(),
  947.  947                     MATH_BIGINTEGER_SIGN => false
  948.  948                 );
  949.  949             }
  950.  950 
  951.  951             $temp $this->_subtract($x_valuefalse$y_valuefalse);
  952.  952             $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_valuefalse$y_valuefalse) > ?
  953.  953                                           $x_negative $y_negative;
  954.  954 
  955.  955             return $temp;
  956.  956         }
  957.  957 
  958.  958         if ($x_size $y_size) {
  959.  959             $size $x_size;
  960.  960             $value $y_value;
  961.  961         } else {
  962.  962             $size $y_size;
  963.  963             $value $x_value;
  964.  964         }
  965.  965 
  966.  966         $value[count($value)] = 0// just in case the carry adds an extra digit
  967.  967 
  968.  968         $carry 0;
  969.  969         for ($i 0$j 1$j $size$i+=2$j+=2) {
  970.  970             $sum $x_value[$j] * MATH_BIGINTEGER_BASE_FULL $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL $y_value[$i] + $carry;
  971.  971             $carry $sum >= MATH_BIGINTEGER_MAX_DIGIT2// eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
  972.  972             $sum $carry $sum MATH_BIGINTEGER_MAX_DIGIT2 $sum;
  973.  973 
  974.  974             $temp MATH_BIGINTEGER_BASE === 26 intval($sum 0x4000000) : ($sum >> 31);
  975.  975 
  976.  976             $value[$i] = (int) ($sum MATH_BIGINTEGER_BASE_FULL $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
  977.  977             $value[$j] = $temp;
  978.  978         }
  979.  979 
  980.  980         if ($j == $size) { // ie. if $y_size is odd
  981.  981             $sum $x_value[$i] + $y_value[$i] + $carry;
  982.  982             $carry $sum >= MATH_BIGINTEGER_BASE_FULL;
  983.  983             $value[$i] = $carry $sum MATH_BIGINTEGER_BASE_FULL $sum;
  984.  984             ++$i// ie. let $i = $j since we've just done $value[$i]
  985.  985         }
  986.  986 
  987.  987         if ($carry) {
  988.  988             for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) {
  989.  989                 $value[$i] = 0;
  990.  990             }
  991.  991             ++$value[$i];
  992.  992         }
  993.  993 
  994.  994         return array(
  995.  995             MATH_BIGINTEGER_VALUE => $this->_trim($value),
  996.  996             MATH_BIGINTEGER_SIGN => $x_negative
  997.  997         );
  998.  998     }
  999.  999 
  1000. 1000     /**
  1001. 1001      * Subtracts two BigIntegers.
  1002. 1002      *
  1003. 1003      * Here's an example:
  1004. 1004      * <code>
  1005. 1005      * <?php
  1006. 1006      *    include 'Math/BigInteger.php';
  1007. 1007      *
  1008. 1008      *    $a = new Math_BigInteger('10');
  1009. 1009      *    $b = new Math_BigInteger('20');
  1010. 1010      *
  1011. 1011      *    $c = $a->subtract($b);
  1012. 1012      *
  1013. 1013      *    echo $c->toString(); // outputs -10
  1014. 1014      * ?>
  1015. 1015      * </code>
  1016. 1016      *
  1017. 1017      * @param Math_BigInteger $y
  1018. 1018      * @return Math_BigInteger
  1019. 1019      * @access public
  1020. 1020      * @internal Performs base-2**52 subtraction
  1021. 1021      */
  1022. 1022     function subtract($y)
  1023. 1023     {
  1024. 1024         switch (MATH_BIGINTEGER_MODE) {
  1025. 1025             case MATH_BIGINTEGER_MODE_GMP:
  1026. 1026                 $temp = new Math_BigInteger();
  1027. 1027                 $temp->value gmp_sub($this->value$y->value);
  1028. 1028 
  1029. 1029                 return $this->_normalize($temp);
  1030. 1030             case MATH_BIGINTEGER_MODE_BCMATH:
  1031. 1031                 $temp = new Math_BigInteger();
  1032. 1032                 $temp->value bcsub($this->value$y->value0);
  1033. 1033 
  1034. 1034                 return $this->_normalize($temp);
  1035. 1035         }
  1036. 1036 
  1037. 1037         $temp $this->_subtract($this->value$this->is_negative$y->value$y->is_negative);
  1038. 1038 
  1039. 1039         $result = new Math_BigInteger();
  1040. 1040         $result->value $temp[MATH_BIGINTEGER_VALUE];
  1041. 1041         $result->is_negative $temp[MATH_BIGINTEGER_SIGN];
  1042. 1042 
  1043. 1043         return $this->_normalize($result);
  1044. 1044     }
  1045. 1045 
  1046. 1046     /**
  1047. 1047      * Performs subtraction.
  1048. 1048      *
  1049. 1049      * @param array $x_value
  1050. 1050      * @param bool $x_negative
  1051. 1051      * @param array $y_value
  1052. 1052      * @param bool $y_negative
  1053. 1053      * @return array
  1054. 1054      * @access private
  1055. 1055      */
  1056. 1056     function _subtract($x_value$x_negative$y_value$y_negative)
  1057. 1057     {
  1058. 1058         $x_size count($x_value);
  1059. 1059         $y_size count($y_value);
  1060. 1060 
  1061. 1061         if ($x_size == 0) {
  1062. 1062             return array(
  1063. 1063                 MATH_BIGINTEGER_VALUE => $y_value,
  1064. 1064                 MATH_BIGINTEGER_SIGN => !$y_negative
  1065. 1065             );
  1066. 1066         } elseif ($y_size == 0) {
  1067. 1067             return array(
  1068. 1068                 MATH_BIGINTEGER_VALUE => $x_value,
  1069. 1069                 MATH_BIGINTEGER_SIGN => $x_negative
  1070. 1070             );
  1071. 1071         }
  1072. 1072 
  1073. 1073         // add, if appropriate (ie. -$x - +$y or +$x - -$y)
  1074. 1074         if ($x_negative != $y_negative) {
  1075. 1075             $temp $this->_add($x_valuefalse$y_valuefalse);
  1076. 1076             $temp[MATH_BIGINTEGER_SIGN] = $x_negative;
  1077. 1077 
  1078. 1078             return $temp;
  1079. 1079         }
  1080. 1080 
  1081. 1081         $diff $this->_compare($x_value$x_negative$y_value$y_negative);
  1082. 1082 
  1083. 1083         if (!$diff) {
  1084. 1084             return array(
  1085. 1085                 MATH_BIGINTEGER_VALUE => array(),
  1086. 1086                 MATH_BIGINTEGER_SIGN => false
  1087. 1087             );
  1088. 1088         }
  1089. 1089 
  1090. 1090         // switch $x and $y around, if appropriate.
  1091. 1091         if ((!$x_negative && $diff 0) || ($x_negative && $diff 0)) {
  1092. 1092             $temp $x_value;
  1093. 1093             $x_value $y_value;
  1094. 1094             $y_value $temp;
  1095. 1095 
  1096. 1096             $x_negative = !$x_negative;
  1097. 1097 
  1098. 1098             $x_size count($x_value);
  1099. 1099             $y_size count($y_value);
  1100. 1100         }
  1101. 1101 
  1102. 1102         // at this point, $x_value should be at least as big as - if not bigger than - $y_value
  1103. 1103 
  1104. 1104         $carry 0;
  1105. 1105         for ($i 0$j 1$j $y_size$i+=2$j+=2) {
  1106. 1106             $sum $x_value[$j] * MATH_BIGINTEGER_BASE_FULL $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL $y_value[$i] - $carry;
  1107. 1107             $carry $sum 0// eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
  1108. 1108             $sum $carry $sum MATH_BIGINTEGER_MAX_DIGIT2 $sum;
  1109. 1109 
  1110. 1110             $temp MATH_BIGINTEGER_BASE === 26 intval($sum 0x4000000) : ($sum >> 31);
  1111. 1111 
  1112. 1112             $x_value[$i] = (int) ($sum MATH_BIGINTEGER_BASE_FULL $temp);
  1113. 1113             $x_value[$j] = $temp;
  1114. 1114         }
  1115. 1115 
  1116. 1116         if ($j == $y_size) { // ie. if $y_size is odd
  1117. 1117             $sum $x_value[$i] - $y_value[$i] - $carry;
  1118. 1118             $carry $sum 0;
  1119. 1119             $x_value[$i] = $carry $sum MATH_BIGINTEGER_BASE_FULL $sum;
  1120. 1120             ++$i;
  1121. 1121         }
  1122. 1122 
  1123. 1123         if ($carry) {
  1124. 1124             for (; !$x_value[$i]; ++$i) {
  1125. 1125                 $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
  1126. 1126             }
  1127. 1127             --$x_value[$i];
  1128. 1128         }
  1129. 1129 
  1130. 1130         return array(
  1131. 1131             MATH_BIGINTEGER_VALUE => $this->_trim($x_value),
  1132. 1132             MATH_BIGINTEGER_SIGN => $x_negative
  1133. 1133         );
  1134. 1134     }
  1135. 1135 
  1136. 1136     /**
  1137. 1137      * Multiplies two BigIntegers
  1138. 1138      *
  1139. 1139      * Here's an example:
  1140. 1140      * <code>
  1141. 1141      * <?php
  1142. 1142      *    include 'Math/BigInteger.php';
  1143. 1143      *
  1144. 1144      *    $a = new Math_BigInteger('10');
  1145. 1145      *    $b = new Math_BigInteger('20');
  1146. 1146      *
  1147. 1147      *    $c = $a->multiply($b);
  1148. 1148      *
  1149. 1149      *    echo $c->toString(); // outputs 200
  1150. 1150      * ?>
  1151. 1151      * </code>
  1152. 1152      *
  1153. 1153      * @param Math_BigInteger $x
  1154. 1154      * @return Math_BigInteger
  1155. 1155      * @access public
  1156. 1156      */
  1157. 1157     function multiply($x)
  1158. 1158     {
  1159. 1159         switch (MATH_BIGINTEGER_MODE) {
  1160. 1160             case MATH_BIGINTEGER_MODE_GMP:
  1161. 1161                 $temp = new Math_BigInteger();
  1162. 1162                 $temp->value gmp_mul($this->value$x->value);
  1163. 1163 
  1164. 1164                 return $this->_normalize($temp);
  1165. 1165             case MATH_BIGINTEGER_MODE_BCMATH:
  1166. 1166                 $temp = new Math_BigInteger();
  1167. 1167                 $temp->value bcmul($this->value$x->value0);
  1168. 1168 
  1169. 1169                 return $this->_normalize($temp);
  1170. 1170         }
  1171. 1171 
  1172. 1172         $temp $this->_multiply($this->value$this->is_negative$x->value$x->is_negative);
  1173. 1173 
  1174. 1174         $product = new Math_BigInteger();
  1175. 1175         $product->value $temp[MATH_BIGINTEGER_VALUE];
  1176. 1176         $product->is_negative $temp[MATH_BIGINTEGER_SIGN];
  1177. 1177 
  1178. 1178         return $this->_normalize($product);
  1179. 1179     }
  1180. 1180 
  1181. 1181     /**
  1182. 1182      * Performs multiplication.
  1183. 1183      *
  1184. 1184      * @param array $x_value
  1185. 1185      * @param bool $x_negative
  1186. 1186      * @param array $y_value
  1187. 1187      * @param bool $y_negative
  1188. 1188      * @return array
  1189. 1189      * @access private
  1190. 1190      */
  1191. 1191     function _multiply($x_value$x_negative$y_value$y_negative)
  1192. 1192     {
  1193. 1193         //if ( $x_value == $y_value ) {
  1194. 1194         //    return array(
  1195. 1195         //        MATH_BIGINTEGER_VALUE => $this->_square($x_value),
  1196. 1196         //        MATH_BIGINTEGER_SIGN => $x_sign != $y_value
  1197. 1197         //    );
  1198. 1198         //}
  1199. 1199 
  1200. 1200         $x_length count($x_value);
  1201. 1201         $y_length count($y_value);
  1202. 1202 
  1203. 1203         if (!$x_length || !$y_length) { // a 0 is being multiplied
  1204. 1204             return array(
  1205. 1205                 MATH_BIGINTEGER_VALUE => array(),
  1206. 1206                 MATH_BIGINTEGER_SIGN => false
  1207. 1207             );
  1208. 1208         }
  1209. 1209 
  1210. 1210         return array(
  1211. 1211             MATH_BIGINTEGER_VALUE => min($x_length$y_length) < MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
  1212. 1212                 $this->_trim($this->_regularMultiply($x_value$y_value)) :
  1213. 1213                 $this->_trim($this->_karatsuba($x_value$y_value)),
  1214. 1214             MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
  1215. 1215         );
  1216. 1216     }
  1217. 1217 
  1218. 1218     /**
  1219. 1219      * Performs long multiplication on two BigIntegers
  1220. 1220      *
  1221. 1221      * Modeled after 'multiply' in MutableBigInteger.java.
  1222. 1222      *
  1223. 1223      * @param array $x_value
  1224. 1224      * @param array $y_value
  1225. 1225      * @return array
  1226. 1226      * @access private
  1227. 1227      */
  1228. 1228     function _regularMultiply($x_value$y_value)
  1229. 1229     {
  1230. 1230         $x_length count($x_value);
  1231. 1231         $y_length count($y_value);
  1232. 1232 
  1233. 1233         if (!$x_length || !$y_length) { // a 0 is being multiplied
  1234. 1234             return array();
  1235. 1235         }
  1236. 1236 
  1237. 1237         if ($x_length $y_length) {
  1238. 1238             $temp $x_value;
  1239. 1239             $x_value $y_value;
  1240. 1240             $y_value $temp;
  1241. 1241 
  1242. 1242             $x_length count($x_value);
  1243. 1243             $y_length count($y_value);
  1244. 1244         }
  1245. 1245 
  1246. 1246         $product_value $this->_array_repeat(0$x_length $y_length);
  1247. 1247 
  1248. 1248         // the following for loop could be removed if the for loop following it
  1249. 1249         // (the one with nested for loops) initially set $i to 0, but
  1250. 1250         // doing so would also make the result in one set of unnecessary adds,
  1251. 1251         // since on the outermost loops first pass, $product->value[$k] is going
  1252. 1252         // to always be 0
  1253. 1253 
  1254. 1254         $carry 0;
  1255. 1255 
  1256. 1256         for ($j 0$j $x_length; ++$j) { // ie. $i = 0
  1257. 1257             $temp $x_value[$j] * $y_value[0] + $carry// $product_value[$k] == 0
  1258. 1258             $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  1259. 1259             $product_value[$j] = (int) ($temp MATH_BIGINTEGER_BASE_FULL $carry);
  1260. 1260         }
  1261. 1261 
  1262. 1262         $product_value[$j] = $carry;
  1263. 1263 
  1264. 1264         // the above for loop is what the previous comment was talking about.  the
  1265. 1265         // following for loop is the "one with nested for loops"
  1266. 1266         for ($i 1$i $y_length; ++$i) {
  1267. 1267             $carry 0;
  1268. 1268 
  1269. 1269             for ($j 0$k $i$j $x_length; ++$j, ++$k) {
  1270. 1270                 $temp $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  1271. 1271                 $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  1272. 1272                 $product_value[$k] = (int) ($temp MATH_BIGINTEGER_BASE_FULL $carry);
  1273. 1273             }
  1274. 1274 
  1275. 1275             $product_value[$k] = $carry;
  1276. 1276         }
  1277. 1277 
  1278. 1278         return $product_value;
  1279. 1279     }
  1280. 1280 
  1281. 1281     /**
  1282. 1282      * Performs Karatsuba multiplication on two BigIntegers
  1283. 1283      *
  1284. 1284      * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  1285. 1285      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
  1286. 1286      *
  1287. 1287      * @param array $x_value
  1288. 1288      * @param array $y_value
  1289. 1289      * @return array
  1290. 1290      * @access private
  1291. 1291      */
  1292. 1292     function _karatsuba($x_value$y_value)
  1293. 1293     {
  1294. 1294         $m min(count($x_value) >> 1count($y_value) >> 1);
  1295. 1295 
  1296. 1296         if ($m MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
  1297. 1297             return $this->_regularMultiply($x_value$y_value);
  1298. 1298         }
  1299. 1299 
  1300. 1300         $x1 array_slice($x_value$m);
  1301. 1301         $x0 array_slice($x_value0$m);
  1302. 1302         $y1 array_slice($y_value$m);
  1303. 1303         $y0 array_slice($y_value0$m);
  1304. 1304 
  1305. 1305         $z2 $this->_karatsuba($x1$y1);
  1306. 1306         $z0 $this->_karatsuba($x0$y0);
  1307. 1307 
  1308. 1308         $z1 $this->_add($x1false$x0false);
  1309. 1309         $temp $this->_add($y1false$y0false);
  1310. 1310         $z1 $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
  1311. 1311         $temp $this->_add($z2false$z0false);
  1312. 1312         $z1 $this->_subtract($z1false$temp[MATH_BIGINTEGER_VALUE], false);
  1313. 1313 
  1314. 1314         $z2 array_merge(array_fill(0$m0), $z2);
  1315. 1315         $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0$m0), $z1[MATH_BIGINTEGER_VALUE]);
  1316. 1316 
  1317. 1317         $xy $this->_add($z2false$z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
  1318. 1318         $xy $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0false);
  1319. 1319 
  1320. 1320         return $xy[MATH_BIGINTEGER_VALUE];
  1321. 1321     }
  1322. 1322 
  1323. 1323     /**
  1324. 1324      * Performs squaring
  1325. 1325      *
  1326. 1326      * @param array $x
  1327. 1327      * @return array
  1328. 1328      * @access private
  1329. 1329      */
  1330. 1330     function _square($x false)
  1331. 1331     {
  1332. 1332         return count($x) < MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
  1333. 1333             $this->_trim($this->_baseSquare($x)) :
  1334. 1334             $this->_trim($this->_karatsubaSquare($x));
  1335. 1335     }
  1336. 1336 
  1337. 1337     /**
  1338. 1338      * Performs traditional squaring on two BigIntegers
  1339. 1339      *
  1340. 1340      * Squaring can be done faster than multiplying a number by itself can be.  See
  1341. 1341      * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
  1342. 1342      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
  1343. 1343      *
  1344. 1344      * @param array $value
  1345. 1345      * @return array
  1346. 1346      * @access private
  1347. 1347      */
  1348. 1348     function _baseSquare($value)
  1349. 1349     {
  1350. 1350         if (empty($value)) {
  1351. 1351             return array();
  1352. 1352         }
  1353. 1353         $square_value $this->_array_repeat(0count($value));
  1354. 1354 
  1355. 1355         for ($i 0$max_index count($value) - 1$i <= $max_index; ++$i) {
  1356. 1356             $i2 $i << 1;
  1357. 1357 
  1358. 1358             $temp $square_value[$i2] + $value[$i] * $value[$i];
  1359. 1359             $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  1360. 1360             $square_value[$i2] = (int) ($temp MATH_BIGINTEGER_BASE_FULL $carry);
  1361. 1361 
  1362. 1362             // note how we start from $i+1 instead of 0 as we do in multiplication.
  1363. 1363             for ($j $i 1$k $i2 1$j <= $max_index; ++$j, ++$k) {
  1364. 1364                 $temp $square_value[$k] + $value[$j] * $value[$i] + $carry;
  1365. 1365                 $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  1366. 1366                 $square_value[$k] = (int) ($temp MATH_BIGINTEGER_BASE_FULL $carry);
  1367. 1367             }
  1368. 1368 
  1369. 1369             // the following line can yield values larger 2**15.  at this point, PHP should switch
  1370. 1370             // over to floats.
  1371. 1371             $square_value[$i $max_index 1] = $carry;
  1372. 1372         }
  1373. 1373 
  1374. 1374         return $square_value;
  1375. 1375     }
  1376. 1376 
  1377. 1377     /**
  1378. 1378      * Performs Karatsuba "squaring" on two BigIntegers
  1379. 1379      *
  1380. 1380      * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  1381. 1381      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
  1382. 1382      *
  1383. 1383      * @param array $value
  1384. 1384      * @return array
  1385. 1385      * @access private
  1386. 1386      */
  1387. 1387     function _karatsubaSquare($value)
  1388. 1388     {
  1389. 1389         $m count($value) >> 1;
  1390. 1390 
  1391. 1391         if ($m MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
  1392. 1392             return $this->_baseSquare($value);
  1393. 1393         }
  1394. 1394 
  1395. 1395         $x1 array_slice($value$m);
  1396. 1396         $x0 array_slice($value0$m);
  1397. 1397 
  1398. 1398         $z2 $this->_karatsubaSquare($x1);
  1399. 1399         $z0 $this->_karatsubaSquare($x0);
  1400. 1400 
  1401. 1401         $z1 $this->_add($x1false$x0false);
  1402. 1402         $z1 $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
  1403. 1403         $temp $this->_add($z2false$z0false);
  1404. 1404         $z1 $this->_subtract($z1false$temp[MATH_BIGINTEGER_VALUE], false);
  1405. 1405 
  1406. 1406         $z2 array_merge(array_fill(0$m0), $z2);
  1407. 1407         $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0$m0), $z1[MATH_BIGINTEGER_VALUE]);
  1408. 1408 
  1409. 1409         $xx $this->_add($z2false$z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
  1410. 1410         $xx $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0false);
  1411. 1411 
  1412. 1412         return $xx[MATH_BIGINTEGER_VALUE];
  1413. 1413     }
  1414. 1414 
  1415. 1415     /**
  1416. 1416      * Divides two BigIntegers.
  1417. 1417      *
  1418. 1418      * Returns an array whose first element contains the quotient and whose second element contains the
  1419. 1419      * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
  1420. 1420      * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
  1421. 1421      * and the divisor (basically, the "common residue" is the first positive modulo).
  1422. 1422      *
  1423. 1423      * Here's an example:
  1424. 1424      * <code>
  1425. 1425      * <?php
  1426. 1426      *    include 'Math/BigInteger.php';
  1427. 1427      *
  1428. 1428      *    $a = new Math_BigInteger('10');
  1429. 1429      *    $b = new Math_BigInteger('20');
  1430. 1430      *
  1431. 1431      *    list($quotient, $remainder) = $a->divide($b);
  1432. 1432      *
  1433. 1433      *    echo $quotient->toString(); // outputs 0
  1434. 1434      *    echo "\r\n";
  1435. 1435      *    echo $remainder->toString(); // outputs 10
  1436. 1436      * ?>
  1437. 1437      * </code>
  1438. 1438      *
  1439. 1439      * @param Math_BigInteger $y
  1440. 1440      * @return array
  1441. 1441      * @access public
  1442. 1442      * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
  1443. 1443      */
  1444. 1444     function divide($y)
  1445. 1445     {
  1446. 1446         switch (MATH_BIGINTEGER_MODE) {
  1447. 1447             case MATH_BIGINTEGER_MODE_GMP:
  1448. 1448                 $quotient = new Math_BigInteger();
  1449. 1449                 $remainder = new Math_BigInteger();
  1450. 1450 
  1451. 1451                 list($quotient->value$remainder->value) = gmp_div_qr($this->value$y->value);
  1452. 1452 
  1453. 1453                 if (gmp_sign($remainder->value) < 0) {
  1454. 1454                     $remainder->value gmp_add($remainder->valuegmp_abs($y->value));
  1455. 1455                 }
  1456. 1456 
  1457. 1457                 return array($this->_normalize($quotient), $this->_normalize($remainder));
  1458. 1458             case MATH_BIGINTEGER_MODE_BCMATH:
  1459. 1459                 $quotient = new Math_BigInteger();
  1460. 1460                 $remainder = new Math_BigInteger();
  1461. 1461 
  1462. 1462                 $quotient->value bcdiv($this->value$y->value0);
  1463. 1463                 $remainder->value bcmod($this->value$y->value);
  1464. 1464 
  1465. 1465                 if ($remainder->value[0] == '-') {
  1466. 1466                     $remainder->value bcadd($remainder->value$y->value[0] == '-' substr($y->value1) : $y->value0);
  1467. 1467                 }
  1468. 1468 
  1469. 1469                 return array($this->_normalize($quotient), $this->_normalize($remainder));
  1470. 1470         }
  1471. 1471 
  1472. 1472         if (count($y->value) == 1) {
  1473. 1473             list($q$r) = $this->_divide_digit($this->value$y->value[0]);
  1474. 1474             $quotient = new Math_BigInteger();
  1475. 1475             $remainder = new Math_BigInteger();
  1476. 1476             $quotient->value $q;
  1477. 1477             $remainder->value = array($r);
  1478. 1478             $quotient->is_negative $this->is_negative != $y->is_negative;
  1479. 1479             return array($this->_normalize($quotient), $this->_normalize($remainder));
  1480. 1480         }
  1481. 1481 
  1482. 1482         static $zero;
  1483. 1483         if (!isset($zero)) {
  1484. 1484             $zero = new Math_BigInteger();
  1485. 1485         }
  1486. 1486 
  1487. 1487         $x $this->copy();
  1488. 1488         $y $y->copy();
  1489. 1489 
  1490. 1490         $x_sign $x->is_negative;
  1491. 1491         $y_sign $y->is_negative;
  1492. 1492 
  1493. 1493         $x->is_negative $y->is_negative false;
  1494. 1494 
  1495. 1495         $diff $x->compare($y);
  1496. 1496 
  1497. 1497         if (!$diff) {
  1498. 1498             $temp = new Math_BigInteger();
  1499. 1499             $temp->value = array(1);
  1500. 1500             $temp->is_negative $x_sign != $y_sign;
  1501. 1501             return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
  1502. 1502         }
  1503. 1503 
  1504. 1504         if ($diff 0) {
  1505. 1505             // if $x is negative, "add" $y.
  1506. 1506             if ($x_sign) {
  1507. 1507                 $x $y->subtract($x);
  1508. 1508             }
  1509. 1509             return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
  1510. 1510         }
  1511. 1511 
  1512. 1512         // normalize $x and $y as described in HAC 14.23 / 14.24
  1513. 1513         $msb $y->value[count($y->value) - 1];
  1514. 1514         for ($shift 0; !($msb MATH_BIGINTEGER_MSB); ++$shift) {
  1515. 1515             $msb <<= 1;
  1516. 1516         }
  1517. 1517         $x->_lshift($shift);
  1518. 1518         $y->_lshift($shift);
  1519. 1519         $y_value = &$y->value;
  1520. 1520 
  1521. 1521         $x_max count($x->value) - 1;
  1522. 1522         $y_max count($y->value) - 1;
  1523. 1523 
  1524. 1524         $quotient = new Math_BigInteger();
  1525. 1525         $quotient_value = &$quotient->value;
  1526. 1526         $quotient_value $this->_array_repeat(0$x_max $y_max 1);
  1527. 1527 
  1528. 1528         static $temp$lhs$rhs;
  1529. 1529         if (!isset($temp)) {
  1530. 1530             $temp = new Math_BigInteger();
  1531. 1531             $lhs =  new Math_BigInteger();
  1532. 1532             $rhs =  new Math_BigInteger();
  1533. 1533         }
  1534. 1534         $temp_value = &$temp->value;
  1535. 1535         $rhs_value =  &$rhs->value;
  1536. 1536 
  1537. 1537         // $temp = $y << ($x_max - $y_max-1) in base 2**26
  1538. 1538         $temp_value array_merge($this->_array_repeat(0$x_max $y_max), $y_value);
  1539. 1539 
  1540. 1540         while ($x->compare($temp) >= 0) {
  1541. 1541             // calculate the "common residue"
  1542. 1542             ++$quotient_value[$x_max $y_max];
  1543. 1543             $x $x->subtract($temp);
  1544. 1544             $x_max count($x->value) - 1;
  1545. 1545         }
  1546. 1546 
  1547. 1547         for ($i $x_max$i >= $y_max 1; --$i) {
  1548. 1548             $x_value = &$x->value;
  1549. 1549             $x_window = array(
  1550. 1550                 isset($x_value[$i]) ? $x_value[$i] : 0,
  1551. 1551                 isset($x_value[$i 1]) ? $x_value[$i 1] : 0,
  1552. 1552                 isset($x_value[$i 2]) ? $x_value[$i 2] : 0
  1553. 1553             );
  1554. 1554             $y_window = array(
  1555. 1555                 $y_value[$y_max],
  1556. 1556                 ($y_max 0) ? $y_value[$y_max 1] : 0
  1557. 1557             );
  1558. 1558 
  1559. 1559             $q_index $i $y_max 1;
  1560. 1560             if ($x_window[0] == $y_window[0]) {
  1561. 1561                 $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT;
  1562. 1562             } else {
  1563. 1563                 $quotient_value[$q_index] = $this->_safe_divide(
  1564. 1564                     $x_window[0] * MATH_BIGINTEGER_BASE_FULL $x_window[1],
  1565. 1565                     $y_window[0]
  1566. 1566                 );
  1567. 1567             }
  1568. 1568 
  1569. 1569             $temp_value = array($y_window[1], $y_window[0]);
  1570. 1570 
  1571. 1571             $lhs->value = array($quotient_value[$q_index]);
  1572. 1572             $lhs $lhs->multiply($temp);
  1573. 1573 
  1574. 1574             $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
  1575. 1575 
  1576. 1576             while ($lhs->compare($rhs) > 0) {
  1577. 1577                 --$quotient_value[$q_index];
  1578. 1578 
  1579. 1579                 $lhs->value = array($quotient_value[$q_index]);
  1580. 1580                 $lhs $lhs->multiply($temp);
  1581. 1581             }
  1582. 1582 
  1583. 1583             $adjust $this->_array_repeat(0$q_index);
  1584. 1584             $temp_value = array($quotient_value[$q_index]);
  1585. 1585             $temp $temp->multiply($y);
  1586. 1586             $temp_value = &$temp->value;
  1587. 1587             $temp_value array_merge($adjust$temp_value);
  1588. 1588 
  1589. 1589             $x $x->subtract($temp);
  1590. 1590 
  1591. 1591             if ($x->compare($zero) < 0) {
  1592. 1592                 $temp_value array_merge($adjust$y_value);
  1593. 1593                 $x $x->add($temp);
  1594. 1594 
  1595. 1595                 --$quotient_value[$q_index];
  1596. 1596             }
  1597. 1597 
  1598. 1598             $x_max count($x_value) - 1;
  1599. 1599         }
  1600. 1600 
  1601. 1601         // unnormalize the remainder
  1602. 1602         $x->_rshift($shift);
  1603. 1603 
  1604. 1604         $quotient->is_negative $x_sign != $y_sign;
  1605. 1605 
  1606. 1606         // calculate the "common residue", if appropriate
  1607. 1607         if ($x_sign) {
  1608. 1608             $y->_rshift($shift);
  1609. 1609             $x $y->subtract($x);
  1610. 1610         }
  1611. 1611 
  1612. 1612         return array($this->_normalize($quotient), $this->_normalize($x));
  1613. 1613     }
  1614. 1614 
  1615. 1615     /**
  1616. 1616      * Divides a BigInteger by a regular integer
  1617. 1617      *
  1618. 1618      * abc / x = a00 / x + b0 / x + c / x
  1619. 1619      *
  1620. 1620      * @param array $dividend
  1621. 1621      * @param array $divisor
  1622. 1622      * @return array
  1623. 1623      * @access private
  1624. 1624      */
  1625. 1625     function _divide_digit($dividend$divisor)
  1626. 1626     {
  1627. 1627         $carry 0;
  1628. 1628         $result = array();
  1629. 1629 
  1630. 1630         for ($i count($dividend) - 1$i >= 0; --$i) {
  1631. 1631             $temp MATH_BIGINTEGER_BASE_FULL $carry $dividend[$i];
  1632. 1632             $result[$i] = $this->_safe_divide($temp$divisor);
  1633. 1633             $carry = (int) ($temp $divisor $result[$i]);
  1634. 1634         }
  1635. 1635 
  1636. 1636         return array($result$carry);
  1637. 1637     }
  1638. 1638 
  1639. 1639     /**
  1640. 1640      * Performs modular exponentiation.
  1641. 1641      *
  1642. 1642      * Here's an example:
  1643. 1643      * <code>
  1644. 1644      * <?php
  1645. 1645      *    include 'Math/BigInteger.php';
  1646. 1646      *
  1647. 1647      *    $a = new Math_BigInteger('10');
  1648. 1648      *    $b = new Math_BigInteger('20');
  1649. 1649      *    $c = new Math_BigInteger('30');
  1650. 1650      *
  1651. 1651      *    $c = $a->modPow($b, $c);
  1652. 1652      *
  1653. 1653      *    echo $c->toString(); // outputs 10
  1654. 1654      * ?>
  1655. 1655      * </code>
  1656. 1656      *
  1657. 1657      * @param Math_BigInteger $e
  1658. 1658      * @param Math_BigInteger $n
  1659. 1659      * @return Math_BigInteger
  1660. 1660      * @access public
  1661. 1661      * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
  1662. 1662      *    and although the approach involving repeated squaring does vastly better, it, too, is impractical
  1663. 1663      *    for our purposes.  The reason being that division - by far the most complicated and time-consuming
  1664. 1664      *    of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
  1665. 1665      *
  1666. 1666      *    Modular reductions resolve this issue.  Although an individual modular reduction takes more time
  1667. 1667      *    then an individual division, when performed in succession (with the same modulo), they're a lot faster.
  1668. 1668      *
  1669. 1669      *    The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
  1670. 1670      *    although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
  1671. 1671      *    base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
  1672. 1672      *    the product of two odd numbers is odd), but what about when RSA isn't used?
  1673. 1673      *
  1674. 1674      *    In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
  1675. 1675      *    Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
  1676. 1676      *    modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
  1677. 1677      *    uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
  1678. 1678      *    the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
  1679. 1679      *    {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
  1680. 1680      */
  1681. 1681     function modPow($e$n)
  1682. 1682     {
  1683. 1683         $n $this->bitmask !== false && $this->bitmask->compare($n) < $this->bitmask $n->abs();
  1684. 1684 
  1685. 1685         if ($e->compare(new Math_BigInteger()) < 0) {
  1686. 1686             $e $e->abs();
  1687. 1687 
  1688. 1688             $temp $this->modInverse($n);
  1689. 1689             if ($temp === false) {
  1690. 1690                 return false;
  1691. 1691             }
  1692. 1692 
  1693. 1693             return $this->_normalize($temp->modPow($e$n));
  1694. 1694         }
  1695. 1695 
  1696. 1696         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP) {
  1697. 1697             $temp = new Math_BigInteger();
  1698. 1698             $temp->value gmp_powm($this->value$e->value$n->value);
  1699. 1699 
  1700. 1700             return $this->_normalize($temp);
  1701. 1701         }
  1702. 1702 
  1703. 1703         if ($this->compare(new Math_BigInteger()) < || $this->compare($n) > 0) {
  1704. 1704             list(, $temp) = $this->divide($n);
  1705. 1705             return $temp->modPow($e$n);
  1706. 1706         }
  1707. 1707 
  1708. 1708         if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
  1709. 1709             $components = array(
  1710. 1710                 'modulus' => $n->toBytes(true),
  1711. 1711                 'publicExponent' => $e->toBytes(true)
  1712. 1712             );
  1713. 1713 
  1714. 1714             $components = array(
  1715. 1715                 'modulus' => pack('Ca*a*'2$this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
  1716. 1716                 'publicExponent' => pack('Ca*a*'2$this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
  1717. 1717             );
  1718. 1718 
  1719. 1719             $RSAPublicKey pack(
  1720. 1720                 'Ca*a*a*',
  1721. 1721                 48,
  1722. 1722                 $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
  1723. 1723                 $components['modulus'],
  1724. 1724                 $components['publicExponent']
  1725. 1725             );
  1726. 1726 
  1727. 1727             $rsaOID pack('H*''300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
  1728. 1728             $RSAPublicKey chr(0) . $RSAPublicKey;
  1729. 1729             $RSAPublicKey chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
  1730. 1730 
  1731. 1731             $encapsulated pack(
  1732. 1732                 'Ca*a*',
  1733. 1733                 48,
  1734. 1734                 $this->_encodeASN1Length(strlen($rsaOID $RSAPublicKey)),
  1735. 1735                 $rsaOID $RSAPublicKey
  1736. 1736             );
  1737. 1737 
  1738. 1738             $RSAPublicKey "-----BEGIN PUBLIC KEY-----\r\n" .
  1739. 1739                              chunk_split(base64_encode($encapsulated)) .
  1740. 1740                              '-----END PUBLIC KEY-----';
  1741. 1741 
  1742. 1742             $plaintext str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1"\0"STR_PAD_LEFT);
  1743. 1743 
  1744. 1744             if (openssl_public_encrypt($plaintext$result$RSAPublicKeyOPENSSL_NO_PADDING)) {
  1745. 1745                 return new Math_BigInteger($result256);
  1746. 1746             }
  1747. 1747         }
  1748. 1748 
  1749. 1749         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
  1750. 1750             $temp = new Math_BigInteger();
  1751. 1751             $temp->value bcpowmod($this->value$e->value$n->value0);
  1752. 1752 
  1753. 1753             return $this->_normalize($temp);
  1754. 1754         }
  1755. 1755 
  1756. 1756         if (empty($e->value)) {
  1757. 1757             $temp = new Math_BigInteger();
  1758. 1758             $temp->value = array(1);
  1759. 1759             return $this->_normalize($temp);
  1760. 1760         }
  1761. 1761 
  1762. 1762         if ($e->value == array(1)) {
  1763. 1763             list(, $temp) = $this->divide($n);
  1764. 1764             return $this->_normalize($temp);
  1765. 1765         }
  1766. 1766 
  1767. 1767         if ($e->value == array(2)) {
  1768. 1768             $temp = new Math_BigInteger();
  1769. 1769             $temp->value $this->_square($this->value);
  1770. 1770             list(, $temp) = $temp->divide($n);
  1771. 1771             return $this->_normalize($temp);
  1772. 1772         }
  1773. 1773 
  1774. 1774         return $this->_normalize($this->_slidingWindow($e$nMATH_BIGINTEGER_BARRETT));
  1775. 1775 
  1776. 1776         // the following code, although not callable, can be run independently of the above code
  1777. 1777         // although the above code performed better in my benchmarks the following could might
  1778. 1778         // perform better under different circumstances. in lieu of deleting it it's just been
  1779. 1779         // made uncallable
  1780. 1780 
  1781. 1781         // is the modulo odd?
  1782. 1782         if ($n->value[0] & 1) {
  1783. 1783             return $this->_normalize($this->_slidingWindow($e$nMATH_BIGINTEGER_MONTGOMERY));
  1784. 1784         }
  1785. 1785         // if it's not, it's even
  1786. 1786 
  1787. 1787         // find the lowest set bit (eg. the max pow of 2 that divides $n)
  1788. 1788         for ($i 0$i count($n->value); ++$i) {
  1789. 1789             if ($n->value[$i]) {
  1790. 1790                 $temp decbin($n->value[$i]);
  1791. 1791                 $j strlen($temp) - strrpos($temp'1') - 1;
  1792. 1792                 $j+= 26 $i;
  1793. 1793                 break;
  1794. 1794             }
  1795. 1795         }
  1796. 1796         // at this point, 2^$j * $n/(2^$j) == $n
  1797. 1797 
  1798. 1798         $mod1 $n->copy();
  1799. 1799         $mod1->_rshift($j);
  1800. 1800         $mod2 = new Math_BigInteger();
  1801. 1801         $mod2->value = array(1);
  1802. 1802         $mod2->_lshift($j);
  1803. 1803 
  1804. 1804         $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e$mod1MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
  1805. 1805         $part2 $this->_slidingWindow($e$mod2MATH_BIGINTEGER_POWEROF2);
  1806. 1806 
  1807. 1807         $y1 $mod2->modInverse($mod1);
  1808. 1808         $y2 $mod1->modInverse($mod2);
  1809. 1809 
  1810. 1810         $result $part1->multiply($mod2);
  1811. 1811         $result $result->multiply($y1);
  1812. 1812 
  1813. 1813         $temp $part2->multiply($mod1);
  1814. 1814         $temp $temp->multiply($y2);
  1815. 1815 
  1816. 1816         $result $result->add($temp);
  1817. 1817         list(, $result) = $result->divide($n);
  1818. 1818 
  1819. 1819         return $this->_normalize($result);
  1820. 1820     }
  1821. 1821 
  1822. 1822     /**
  1823. 1823      * Performs modular exponentiation.
  1824. 1824      *
  1825. 1825      * Alias for Math_BigInteger::modPow()
  1826. 1826      *
  1827. 1827      * @param Math_BigInteger $e
  1828. 1828      * @param Math_BigInteger $n
  1829. 1829      * @return Math_BigInteger
  1830. 1830      * @access public
  1831. 1831      */
  1832. 1832     function powMod($e$n)
  1833. 1833     {
  1834. 1834         return $this->modPow($e$n);
  1835. 1835     }
  1836. 1836 
  1837. 1837     /**
  1838. 1838      * Sliding Window k-ary Modular Exponentiation
  1839. 1839      *
  1840. 1840      * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
  1841. 1841      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}.  In a departure from those algorithims,
  1842. 1842      * however, this function performs a modular reduction after every multiplication and squaring operation.
  1843. 1843      * As such, this function has the same preconditions that the reductions being used do.
  1844. 1844      *
  1845. 1845      * @param Math_BigInteger $e
  1846. 1846      * @param Math_BigInteger $n
  1847. 1847      * @param int $mode
  1848. 1848      * @return Math_BigInteger
  1849. 1849      * @access private
  1850. 1850      */
  1851. 1851     function _slidingWindow($e$n$mode)
  1852. 1852     {
  1853. 1853         static $window_ranges = array(725812416731793); // from BigInteger.java's oddModPow function
  1854. 1854         //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
  1855. 1855 
  1856. 1856         $e_value $e->value;
  1857. 1857         $e_length count($e_value) - 1;
  1858. 1858         $e_bits decbin($e_value[$e_length]);
  1859. 1859         for ($i $e_length 1$i >= 0; --$i) {
  1860. 1860             $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE'0'STR_PAD_LEFT);
  1861. 1861         }
  1862. 1862 
  1863. 1863         $e_length strlen($e_bits);
  1864. 1864 
  1865. 1865         // calculate the appropriate window size.
  1866. 1866         // $window_size == 3 if $window_ranges is between 25 and 81, for example.
  1867. 1867         for ($i 0$window_size 1$i count($window_ranges) && $e_length $window_ranges[$i]; ++$window_size, ++$i) {
  1868. 1868         }
  1869. 1869 
  1870. 1870         $n_value $n->value;
  1871. 1871 
  1872. 1872         // precompute $this^0 through $this^$window_size
  1873. 1873         $powers = array();
  1874. 1874         $powers[1] = $this->_prepareReduce($this->value$n_value$mode);
  1875. 1875         $powers[2] = $this->_squareReduce($powers[1], $n_value$mode);
  1876. 1876 
  1877. 1877         // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
  1878. 1878         // in a 1.  ie. it's supposed to be odd.
  1879. 1879         $temp << ($window_size 1);
  1880. 1880         for ($i 1$i $temp; ++$i) {
  1881. 1881             $i2 $i << 1;
  1882. 1882             $powers[$i2 1] = $this->_multiplyReduce($powers[$i2 1], $powers[2], $n_value$mode);
  1883. 1883         }
  1884. 1884 
  1885. 1885         $result = array(1);
  1886. 1886         $result $this->_prepareReduce($result$n_value$mode);
  1887. 1887 
  1888. 1888         for ($i 0$i $e_length;) {
  1889. 1889             if (!$e_bits[$i]) {
  1890. 1890                 $result $this->_squareReduce($result$n_value$mode);
  1891. 1891                 ++$i;
  1892. 1892             } else {
  1893. 1893                 for ($j $window_size 1$j 0; --$j) {
  1894. 1894                     if (!empty($e_bits[$i $j])) {
  1895. 1895                         break;
  1896. 1896                     }
  1897. 1897                 }
  1898. 1898 
  1899. 1899                 // eg. the length of substr($e_bits, $i, $j + 1)
  1900. 1900                 for ($k 0$k <= $j; ++$k) {
  1901. 1901                     $result $this->_squareReduce($result$n_value$mode);
  1902. 1902                 }
  1903. 1903 
  1904. 1904                 $result $this->_multiplyReduce($result$powers[bindec(substr($e_bits$i$j 1))], $n_value$mode);
  1905. 1905 
  1906. 1906                 $i += $j 1;
  1907. 1907             }
  1908. 1908         }
  1909. 1909 
  1910. 1910         $temp = new Math_BigInteger();
  1911. 1911         $temp->value $this->_reduce($result$n_value$mode);
  1912. 1912 
  1913. 1913         return $temp;
  1914. 1914     }
  1915. 1915 
  1916. 1916     /**
  1917. 1917      * Modular reduction
  1918. 1918      *
  1919. 1919      * For most $modes this will return the remainder.
  1920. 1920      *
  1921. 1921      * @see self::_slidingWindow()
  1922. 1922      * @access private
  1923. 1923      * @param array $x
  1924. 1924      * @param array $n
  1925. 1925      * @param int $mode
  1926. 1926      * @return array
  1927. 1927      */
  1928. 1928     function _reduce($x$n$mode)
  1929. 1929     {
  1930. 1930         switch ($mode) {
  1931. 1931             case MATH_BIGINTEGER_MONTGOMERY:
  1932. 1932                 return $this->_montgomery($x$n);
  1933. 1933             case MATH_BIGINTEGER_BARRETT:
  1934. 1934                 return $this->_barrett($x$n);
  1935. 1935             case MATH_BIGINTEGER_POWEROF2:
  1936. 1936                 $lhs = new Math_BigInteger();
  1937. 1937                 $lhs->value $x;
  1938. 1938                 $rhs = new Math_BigInteger();
  1939. 1939                 $rhs->value $n;
  1940. 1940                 return $x->_mod2($n);
  1941. 1941             case MATH_BIGINTEGER_CLASSIC:
  1942. 1942                 $lhs = new Math_BigInteger();
  1943. 1943                 $lhs->value $x;
  1944. 1944                 $rhs = new Math_BigInteger();
  1945. 1945                 $rhs->value $n;
  1946. 1946                 list(, $temp) = $lhs->divide($rhs);
  1947. 1947                 return $temp->value;
  1948. 1948             case MATH_BIGINTEGER_NONE:
  1949. 1949                 return $x;
  1950. 1950             default:
  1951. 1951                 // an invalid $mode was provided
  1952. 1952         }
  1953. 1953     }
  1954. 1954 
  1955. 1955     /**
  1956. 1956      * Modular reduction preperation
  1957. 1957      *
  1958. 1958      * @see self::_slidingWindow()
  1959. 1959      * @access private
  1960. 1960      * @param array $x
  1961. 1961      * @param array $n
  1962. 1962      * @param int $mode
  1963. 1963      * @return array
  1964. 1964      */
  1965. 1965     function _prepareReduce($x$n$mode)
  1966. 1966     {
  1967. 1967         if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
  1968. 1968             return $this->_prepMontgomery($x$n);
  1969. 1969         }
  1970. 1970         return $this->_reduce($x$n$mode);
  1971. 1971     }
  1972. 1972 
  1973. 1973     /**
  1974. 1974      * Modular multiply
  1975. 1975      *
  1976. 1976      * @see self::_slidingWindow()
  1977. 1977      * @access private
  1978. 1978      * @param array $x
  1979. 1979      * @param array $y
  1980. 1980      * @param array $n
  1981. 1981      * @param int $mode
  1982. 1982      * @return array
  1983. 1983      */
  1984. 1984     function _multiplyReduce($x$y$n$mode)
  1985. 1985     {
  1986. 1986         if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
  1987. 1987             return $this->_montgomeryMultiply($x$y$n);
  1988. 1988         }
  1989. 1989         $temp $this->_multiply($xfalse$yfalse);
  1990. 1990         return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n$mode);
  1991. 1991     }
  1992. 1992 
  1993. 1993     /**
  1994. 1994      * Modular square
  1995. 1995      *
  1996. 1996      * @see self::_slidingWindow()
  1997. 1997      * @access private
  1998. 1998      * @param array $x
  1999. 1999      * @param array $n
  2000. 2000      * @param int $mode
  2001. 2001      * @return array
  2002. 2002      */
  2003. 2003     function _squareReduce($x$n$mode)
  2004. 2004     {
  2005. 2005         if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
  2006. 2006             return $this->_montgomeryMultiply($x$x$n);
  2007. 2007         }
  2008. 2008         return $this->_reduce($this->_square($x), $n$mode);
  2009. 2009     }
  2010. 2010 
  2011. 2011     /**
  2012. 2012      * Modulos for Powers of Two
  2013. 2013      *
  2014. 2014      * Calculates $x%$n, where $n = 2**$e, for some $e.  Since this is basically the same as doing $x & ($n-1),
  2015. 2015      * we'll just use this function as a wrapper for doing that.
  2016. 2016      *
  2017. 2017      * @see self::_slidingWindow()
  2018. 2018      * @access private
  2019. 2019      * @param Math_BigInteger
  2020. 2020      * @return Math_BigInteger
  2021. 2021      */
  2022. 2022     function _mod2($n)
  2023. 2023     {
  2024. 2024         $temp = new Math_BigInteger();
  2025. 2025         $temp->value = array(1);
  2026. 2026         return $this->bitwise_and($n->subtract($temp));
  2027. 2027     }
  2028. 2028 
  2029. 2029     /**
  2030. 2030      * Barrett Modular Reduction
  2031. 2031      *
  2032. 2032      * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
  2033. 2033      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
  2034. 2034      * so as not to require negative numbers (initially, this script didn't support negative numbers).
  2035. 2035      *
  2036. 2036      * Employs "folding", as described at
  2037. 2037      * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
  2038. 2038      * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
  2039. 2039      *
  2040. 2040      * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
  2041. 2041      * usable on account of (1) its not using reasonable radix points as discussed in
  2042. 2042      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
  2043. 2043      * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
  2044. 2044      * (x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
  2045. 2045      * comments for details.
  2046. 2046      *
  2047. 2047      * @see self::_slidingWindow()
  2048. 2048      * @access private
  2049. 2049      * @param array $n
  2050. 2050      * @param array $m
  2051. 2051      * @return array
  2052. 2052      */
  2053. 2053     function _barrett($n$m)
  2054. 2054     {
  2055. 2055         static $cache = array(
  2056. 2056             MATH_BIGINTEGER_VARIABLE => array(),
  2057. 2057             MATH_BIGINTEGER_DATA => array()
  2058. 2058         );
  2059. 2059 
  2060. 2060         $m_length count($m);
  2061. 2061 
  2062. 2062         // if ($this->_compare($n, $this->_square($m)) >= 0) {
  2063. 2063         if (count($n) > $m_length) {
  2064. 2064             $lhs = new Math_BigInteger();
  2065. 2065             $rhs = new Math_BigInteger();
  2066. 2066             $lhs->value $n;
  2067. 2067             $rhs->value $m;
  2068. 2068             list(, $temp) = $lhs->divide($rhs);
  2069. 2069             return $temp->value;
  2070. 2070         }
  2071. 2071 
  2072. 2072         // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
  2073. 2073         if ($m_length 5) {
  2074. 2074             return $this->_regularBarrett($n$m);
  2075. 2075         }
  2076. 2076 
  2077. 2077         // n = 2 * m.length
  2078. 2078 
  2079. 2079         if (($key array_search($m$cache[MATH_BIGINTEGER_VARIABLE])) === false) {
  2080. 2080             $key count($cache[MATH_BIGINTEGER_VARIABLE]);
  2081. 2081             $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
  2082. 2082 
  2083. 2083             $lhs = new Math_BigInteger();
  2084. 2084             $lhs_value = &$lhs->value;
  2085. 2085             $lhs_value $this->_array_repeat(0$m_length + ($m_length >> 1));
  2086. 2086             $lhs_value[] = 1;
  2087. 2087             $rhs = new Math_BigInteger();
  2088. 2088             $rhs->value $m;
  2089. 2089 
  2090. 2090             list($u$m1) = $lhs->divide($rhs);
  2091. 2091             $u $u->value;
  2092. 2092             $m1 $m1->value;
  2093. 2093 
  2094. 2094             $cache[MATH_BIGINTEGER_DATA][] = array(
  2095. 2095                 'u' => $u// m.length >> 1 (technically (m.length >> 1) + 1)
  2096. 2096                 'm1'=> $m1 // m.length
  2097. 2097             );
  2098. 2098         } else {
  2099. 2099             extract($cache[MATH_BIGINTEGER_DATA][$key]);
  2100. 2100         }
  2101. 2101 
  2102. 2102         $cutoff $m_length + ($m_length >> 1);
  2103. 2103         $lsd array_slice($n0$cutoff); // m.length + (m.length >> 1)
  2104. 2104         $msd array_slice($n$cutoff);    // m.length >> 1
  2105. 2105         $lsd $this->_trim($lsd);
  2106. 2106         $temp $this->_multiply($msdfalse$m1false);
  2107. 2107         $n $this->_add($lsdfalse$temp[MATH_BIGINTEGER_VALUE], false); // m.length + (m.length >> 1) + 1
  2108. 2108 
  2109. 2109         if ($m_length 1) {
  2110. 2110             return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m);
  2111. 2111         }
  2112. 2112 
  2113. 2113         // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
  2114. 2114         $temp array_slice($n[MATH_BIGINTEGER_VALUE], $m_length 1);
  2115. 2115         // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
  2116. 2116         // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
  2117. 2117         $temp $this->_multiply($tempfalse$ufalse);
  2118. 2118         // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
  2119. 2119         // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
  2120. 2120         $temp array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1);
  2121. 2121         // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
  2122. 2122         // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
  2123. 2123         $temp $this->_multiply($tempfalse$mfalse);
  2124. 2124 
  2125. 2125         // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
  2126. 2126         // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
  2127. 2127         // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
  2128. 2128 
  2129. 2129         $result $this->_subtract($n[MATH_BIGINTEGER_VALUE], false$temp[MATH_BIGINTEGER_VALUE], false);
  2130. 2130 
  2131. 2131         while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $mfalse) >= 0) {
  2132. 2132             $result $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $mfalse);
  2133. 2133         }
  2134. 2134 
  2135. 2135         return $result[MATH_BIGINTEGER_VALUE];
  2136. 2136     }
  2137. 2137 
  2138. 2138     /**
  2139. 2139      * (Regular) Barrett Modular Reduction
  2140. 2140      *
  2141. 2141      * For numbers with more than four digits Math_BigInteger::_barrett() is faster.  The difference between that and this
  2142. 2142      * is that this function does not fold the denominator into a smaller form.
  2143. 2143      *
  2144. 2144      * @see self::_slidingWindow()
  2145. 2145      * @access private
  2146. 2146      * @param array $x
  2147. 2147      * @param array $n
  2148. 2148      * @return array
  2149. 2149      */
  2150. 2150     function _regularBarrett($x$n)
  2151. 2151     {
  2152. 2152         static $cache = array(
  2153. 2153             MATH_BIGINTEGER_VARIABLE => array(),
  2154. 2154             MATH_BIGINTEGER_DATA => array()
  2155. 2155         );
  2156. 2156 
  2157. 2157         $n_length count($n);
  2158. 2158 
  2159. 2159         if (count($x) > $n_length) {
  2160. 2160             $lhs = new Math_BigInteger();
  2161. 2161             $rhs = new Math_BigInteger();
  2162. 2162             $lhs->value $x;
  2163. 2163             $rhs->value $n;
  2164. 2164             list(, $temp) = $lhs->divide($rhs);
  2165. 2165             return $temp->value;
  2166. 2166         }
  2167. 2167 
  2168. 2168         if (($key array_search($n$cache[MATH_BIGINTEGER_VARIABLE])) === false) {
  2169. 2169             $key count($cache[MATH_BIGINTEGER_VARIABLE]);
  2170. 2170             $cache[MATH_BIGINTEGER_VARIABLE][] = $n;
  2171. 2171             $lhs = new Math_BigInteger();
  2172. 2172             $lhs_value = &$lhs->value;
  2173. 2173             $lhs_value $this->_array_repeat(0$n_length);
  2174. 2174             $lhs_value[] = 1;
  2175. 2175             $rhs = new Math_BigInteger();
  2176. 2176             $rhs->value $n;
  2177. 2177             list($temp, ) = $lhs->divide($rhs); // m.length
  2178. 2178             $cache[MATH_BIGINTEGER_DATA][] = $temp->value;
  2179. 2179         }
  2180. 2180 
  2181. 2181         // 2 * m.length - (m.length - 1) = m.length + 1
  2182. 2182         $temp array_slice($x$n_length 1);
  2183. 2183         // (m.length + 1) + m.length = 2 * m.length + 1
  2184. 2184         $temp $this->_multiply($tempfalse$cache[MATH_BIGINTEGER_DATA][$key], false);
  2185. 2185         // (2 * m.length + 1) - (m.length - 1) = m.length + 2
  2186. 2186         $temp array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length 1);
  2187. 2187 
  2188. 2188         // m.length + 1
  2189. 2189         $result array_slice($x0$n_length 1);
  2190. 2190         // m.length + 1
  2191. 2191         $temp $this->_multiplyLower($tempfalse$nfalse$n_length 1);
  2192. 2192         // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
  2193. 2193 
  2194. 2194         if ($this->_compare($resultfalse$temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) {
  2195. 2195             $corrector_value $this->_array_repeat(0$n_length 1);
  2196. 2196             $corrector_value[count($corrector_value)] = 1;
  2197. 2197             $result $this->_add($resultfalse$corrector_valuefalse);
  2198. 2198             $result $result[MATH_BIGINTEGER_VALUE];
  2199. 2199         }
  2200. 2200 
  2201. 2201         // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
  2202. 2202         $result $this->_subtract($resultfalse$temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]);
  2203. 2203         while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $nfalse) > 0) {
  2204. 2204             $result $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $nfalse);
  2205. 2205         }
  2206. 2206 
  2207. 2207         return $result[MATH_BIGINTEGER_VALUE];
  2208. 2208     }
  2209. 2209 
  2210. 2210     /**
  2211. 2211      * Performs long multiplication up to $stop digits
  2212. 2212      *
  2213. 2213      * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
  2214. 2214      *
  2215. 2215      * @see self::_regularBarrett()
  2216. 2216      * @param array $x_value
  2217. 2217      * @param bool $x_negative
  2218. 2218      * @param array $y_value
  2219. 2219      * @param bool $y_negative
  2220. 2220      * @param int $stop
  2221. 2221      * @return array
  2222. 2222      * @access private
  2223. 2223      */
  2224. 2224     function _multiplyLower($x_value$x_negative$y_value$y_negative$stop)
  2225. 2225     {
  2226. 2226         $x_length count($x_value);
  2227. 2227         $y_length count($y_value);
  2228. 2228 
  2229. 2229         if (!$x_length || !$y_length) { // a 0 is being multiplied
  2230. 2230             return array(
  2231. 2231                 MATH_BIGINTEGER_VALUE => array(),
  2232. 2232                 MATH_BIGINTEGER_SIGN => false
  2233. 2233             );
  2234. 2234         }
  2235. 2235 
  2236. 2236         if ($x_length $y_length) {
  2237. 2237             $temp $x_value;
  2238. 2238             $x_value $y_value;
  2239. 2239             $y_value $temp;
  2240. 2240 
  2241. 2241             $x_length count($x_value);
  2242. 2242             $y_length count($y_value);
  2243. 2243         }
  2244. 2244 
  2245. 2245         $product_value $this->_array_repeat(0$x_length $y_length);
  2246. 2246 
  2247. 2247         // the following for loop could be removed if the for loop following it
  2248. 2248         // (the one with nested for loops) initially set $i to 0, but
  2249. 2249         // doing so would also make the result in one set of unnecessary adds,
  2250. 2250         // since on the outermost loops first pass, $product->value[$k] is going
  2251. 2251         // to always be 0
  2252. 2252 
  2253. 2253         $carry 0;
  2254. 2254 
  2255. 2255         for ($j 0$j $x_length; ++$j) { // ie. $i = 0, $k = $i
  2256. 2256             $temp $x_value[$j] * $y_value[0] + $carry// $product_value[$k] == 0
  2257. 2257             $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  2258. 2258             $product_value[$j] = (int) ($temp MATH_BIGINTEGER_BASE_FULL $carry);
  2259. 2259         }
  2260. 2260 
  2261. 2261         if ($j $stop) {
  2262. 2262             $product_value[$j] = $carry;
  2263. 2263         }
  2264. 2264 
  2265. 2265         // the above for loop is what the previous comment was talking about.  the
  2266. 2266         // following for loop is the "one with nested for loops"
  2267. 2267 
  2268. 2268         for ($i 1$i $y_length; ++$i) {
  2269. 2269             $carry 0;
  2270. 2270 
  2271. 2271             for ($j 0$k $i$j $x_length && $k $stop; ++$j, ++$k) {
  2272. 2272                 $temp $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  2273. 2273                 $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  2274. 2274                 $product_value[$k] = (int) ($temp MATH_BIGINTEGER_BASE_FULL $carry);
  2275. 2275             }
  2276. 2276 
  2277. 2277             if ($k $stop) {
  2278. 2278                 $product_value[$k] = $carry;
  2279. 2279             }
  2280. 2280         }
  2281. 2281 
  2282. 2282         return array(
  2283. 2283             MATH_BIGINTEGER_VALUE => $this->_trim($product_value),
  2284. 2284             MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
  2285. 2285         );
  2286. 2286     }
  2287. 2287 
  2288. 2288     /**
  2289. 2289      * Montgomery Modular Reduction
  2290. 2290      *
  2291. 2291      * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
  2292. 2292      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
  2293. 2293      * improved upon (basically, by using the comba method).  gcd($n, 2) must be equal to one for this function
  2294. 2294      * to work correctly.
  2295. 2295      *
  2296. 2296      * @see self::_prepMontgomery()
  2297. 2297      * @see self::_slidingWindow()
  2298. 2298      * @access private
  2299. 2299      * @param array $x
  2300. 2300      * @param array $n
  2301. 2301      * @return array
  2302. 2302      */
  2303. 2303     function _montgomery($x$n)
  2304. 2304     {
  2305. 2305         static $cache = array(
  2306. 2306             MATH_BIGINTEGER_VARIABLE => array(),
  2307. 2307             MATH_BIGINTEGER_DATA => array()
  2308. 2308         );
  2309. 2309 
  2310. 2310         if (($key array_search($n$cache[MATH_BIGINTEGER_VARIABLE])) === false) {
  2311. 2311             $key count($cache[MATH_BIGINTEGER_VARIABLE]);
  2312. 2312             $cache[MATH_BIGINTEGER_VARIABLE][] = $x;
  2313. 2313             $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n);
  2314. 2314         }
  2315. 2315 
  2316. 2316         $k count($n);
  2317. 2317 
  2318. 2318         $result = array(MATH_BIGINTEGER_VALUE => $x);
  2319. 2319 
  2320. 2320         for ($i 0$i $k; ++$i) {
  2321. 2321             $temp $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key];
  2322. 2322             $temp $temp MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31));
  2323. 2323             $temp $this->_regularMultiply(array($temp), $n);
  2324. 2324             $temp array_merge($this->_array_repeat(0$i), $temp);
  2325. 2325             $result $this->_add($result[MATH_BIGINTEGER_VALUE], false$tempfalse);
  2326. 2326         }
  2327. 2327 
  2328. 2328         $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k);
  2329. 2329 
  2330. 2330         if ($this->_compare($resultfalse$nfalse) >= 0) {
  2331. 2331             $result $this->_subtract($result[MATH_BIGINTEGER_VALUE], false$nfalse);
  2332. 2332         }
  2333. 2333 
  2334. 2334         return $result[MATH_BIGINTEGER_VALUE];
  2335. 2335     }
  2336. 2336 
  2337. 2337     /**
  2338. 2338      * Montgomery Multiply
  2339. 2339      *
  2340. 2340      * Interleaves the montgomery reduction and long multiplication algorithms together as described in
  2341. 2341      * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
  2342. 2342      *
  2343. 2343      * @see self::_prepMontgomery()
  2344. 2344      * @see self::_montgomery()
  2345. 2345      * @access private
  2346. 2346      * @param array $x
  2347. 2347      * @param array $y
  2348. 2348      * @param array $m
  2349. 2349      * @return array
  2350. 2350      */
  2351. 2351     function _montgomeryMultiply($x$y$m)
  2352. 2352     {
  2353. 2353         $temp $this->_multiply($xfalse$yfalse);
  2354. 2354         return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m);
  2355. 2355 
  2356. 2356         // the following code, although not callable, can be run independently of the above code
  2357. 2357         // although the above code performed better in my benchmarks the following could might
  2358. 2358         // perform better under different circumstances. in lieu of deleting it it's just been
  2359. 2359         // made uncallable
  2360. 2360 
  2361. 2361         static $cache = array(
  2362. 2362             MATH_BIGINTEGER_VARIABLE => array(),
  2363. 2363             MATH_BIGINTEGER_DATA => array()
  2364. 2364         );
  2365. 2365 
  2366. 2366         if (($key array_search($m$cache[MATH_BIGINTEGER_VARIABLE])) === false) {
  2367. 2367             $key count($cache[MATH_BIGINTEGER_VARIABLE]);
  2368. 2368             $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
  2369. 2369             $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m);
  2370. 2370         }
  2371. 2371 
  2372. 2372         $n max(count($x), count($y), count($m));
  2373. 2373         $x array_pad($x$n0);
  2374. 2374         $y array_pad($y$n0);
  2375. 2375         $m array_pad($m$n0);
  2376. 2376         $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0$n 1));
  2377. 2377         for ($i 0$i $n; ++$i) {
  2378. 2378             $temp $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0];
  2379. 2379             $temp $temp MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31));
  2380. 2380             $temp $temp $cache[MATH_BIGINTEGER_DATA][$key];
  2381. 2381             $temp $temp MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31));
  2382. 2382             $temp $this->_add($this->_regularMultiply(array($x[$i]), $y), false$this->_regularMultiply(array($temp), $m), false);
  2383. 2383             $a $this->_add($a[MATH_BIGINTEGER_VALUE], false$temp[MATH_BIGINTEGER_VALUE], false);
  2384. 2384             $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1);
  2385. 2385         }
  2386. 2386         if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false$mfalse) >= 0) {
  2387. 2387             $a $this->_subtract($a[MATH_BIGINTEGER_VALUE], false$mfalse);
  2388. 2388         }
  2389. 2389         return $a[MATH_BIGINTEGER_VALUE];
  2390. 2390     }
  2391. 2391 
  2392. 2392     /**
  2393. 2393      * Prepare a number for use in Montgomery Modular Reductions
  2394. 2394      *
  2395. 2395      * @see self::_montgomery()
  2396. 2396      * @see self::_slidingWindow()
  2397. 2397      * @access private
  2398. 2398      * @param array $x
  2399. 2399      * @param array $n
  2400. 2400      * @return array
  2401. 2401      */
  2402. 2402     function _prepMontgomery($x$n)
  2403. 2403     {
  2404. 2404         $lhs = new Math_BigInteger();
  2405. 2405         $lhs->value array_merge($this->_array_repeat(0count($n)), $x);
  2406. 2406         $rhs = new Math_BigInteger();
  2407. 2407         $rhs->value $n;
  2408. 2408 
  2409. 2409         list(, $temp) = $lhs->divide($rhs);
  2410. 2410         return $temp->value;
  2411. 2411     }
  2412. 2412 
  2413. 2413     /**
  2414. 2414      * Modular Inverse of a number mod 2**26 (eg. 67108864)
  2415. 2415      *
  2416. 2416      * Based off of the bnpInvDigit function implemented and justified in the following URL:
  2417. 2417      *
  2418. 2418      * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
  2419. 2419      *
  2420. 2420      * The following URL provides more info:
  2421. 2421      *
  2422. 2422      * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
  2423. 2423      *
  2424. 2424      * As for why we do all the bitmasking...  strange things can happen when converting from floats to ints. For
  2425. 2425      * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
  2426. 2426      * int(-2147483648).  To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
  2427. 2427      * auto-converted to floats.  The outermost bitmask is present because without it, there's no guarantee that
  2428. 2428      * the "residue" returned would be the so-called "common residue".  We use fmod, in the last step, because the
  2429. 2429      * maximum possible $x is 26 bits and the maximum $result is 16 bits.  Thus, we have to be able to handle up to
  2430. 2430      * 40 bits, which only 64-bit floating points will support.
  2431. 2431      *
  2432. 2432      * Thanks to Pedro Gimeno Fortea for input!
  2433. 2433      *
  2434. 2434      * @see self::_montgomery()
  2435. 2435      * @access private
  2436. 2436      * @param array $x
  2437. 2437      * @return int
  2438. 2438      */
  2439. 2439     function _modInverse67108864($x// 2**26 == 67,108,864
  2440. 2440     {
  2441. 2441         $x = -$x[0];
  2442. 2442         $result $x 0x3// x**-1 mod 2**2
  2443. 2443         $result = ($result * ($x $result)) & 0xF// x**-1 mod 2**4
  2444. 2444         $result = ($result * (- ($x 0xFF) * $result))  & 0xFF// x**-1 mod 2**8
  2445. 2445         $result = ($result * ((- ($x 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF// x**-1 mod 2**16
  2446. 2446         $result fmod($result * (fmod($x $resultMATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL); // x**-1 mod 2**26
  2447. 2447         return $result MATH_BIGINTEGER_MAX_DIGIT;
  2448. 2448     }
  2449. 2449 
  2450. 2450     /**
  2451. 2451      * Calculates modular inverses.
  2452. 2452      *
  2453. 2453      * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
  2454. 2454      *
  2455. 2455      * Here's an example:
  2456. 2456      * <code>
  2457. 2457      * <?php
  2458. 2458      *    include 'Math/BigInteger.php';
  2459. 2459      *
  2460. 2460      *    $a = new Math_BigInteger(30);
  2461. 2461      *    $b = new Math_BigInteger(17);
  2462. 2462      *
  2463. 2463      *    $c = $a->modInverse($b);
  2464. 2464      *    echo $c->toString(); // outputs 4
  2465. 2465      *
  2466. 2466      *    echo "\r\n";
  2467. 2467      *
  2468. 2468      *    $d = $a->multiply($c);
  2469. 2469      *    list(, $d) = $d->divide($b);
  2470. 2470      *    echo $d; // outputs 1 (as per the definition of modular inverse)
  2471. 2471      * ?>
  2472. 2472      * </code>
  2473. 2473      *
  2474. 2474      * @param Math_BigInteger $n
  2475. 2475      * @return Math_BigInteger|false
  2476. 2476      * @access public
  2477. 2477      * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
  2478. 2478      */
  2479. 2479     function modInverse($n)
  2480. 2480     {
  2481. 2481         switch (MATH_BIGINTEGER_MODE) {
  2482. 2482             case MATH_BIGINTEGER_MODE_GMP:
  2483. 2483                 $temp = new Math_BigInteger();
  2484. 2484                 $temp->value gmp_invert($this->value$n->value);
  2485. 2485 
  2486. 2486                 return ($temp->value === false) ? false $this->_normalize($temp);
  2487. 2487         }
  2488. 2488 
  2489. 2489         static $zero$one;
  2490. 2490         if (!isset($zero)) {
  2491. 2491             $zero = new Math_BigInteger();
  2492. 2492             $one = new Math_BigInteger(1);
  2493. 2493         }
  2494. 2494 
  2495. 2495         // $x mod -$n == $x mod $n.
  2496. 2496         $n $n->abs();
  2497. 2497 
  2498. 2498         if ($this->compare($zero) < 0) {
  2499. 2499             $temp $this->abs();
  2500. 2500             $temp $temp->modInverse($n);
  2501. 2501             return $this->_normalize($n->subtract($temp));
  2502. 2502         }
  2503. 2503 
  2504. 2504         extract($this->extendedGCD($n));
  2505. 2505 
  2506. 2506         if (!$gcd->equals($one)) {
  2507. 2507             return false;
  2508. 2508         }
  2509. 2509 
  2510. 2510         $x $x->compare($zero) < $x->add($n) : $x;
  2511. 2511 
  2512. 2512         return $this->compare($zero) < $this->_normalize($n->subtract($x)) : $this->_normalize($x);
  2513. 2513     }
  2514. 2514 
  2515. 2515     /**
  2516. 2516      * Calculates the greatest common divisor and Bezout's identity.
  2517. 2517      *
  2518. 2518      * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
  2519. 2519      * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
  2520. 2520      * combination is returned is dependent upon which mode is in use.  See
  2521. 2521      * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
  2522. 2522      *
  2523. 2523      * Here's an example:
  2524. 2524      * <code>
  2525. 2525      * <?php
  2526. 2526      *    include 'Math/BigInteger.php';
  2527. 2527      *
  2528. 2528      *    $a = new Math_BigInteger(693);
  2529. 2529      *    $b = new Math_BigInteger(609);
  2530. 2530      *
  2531. 2531      *    extract($a->extendedGCD($b));
  2532. 2532      *
  2533. 2533      *    echo $gcd->toString() . "\r\n"; // outputs 21
  2534. 2534      *    echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
  2535. 2535      * ?>
  2536. 2536      * </code>
  2537. 2537      *
  2538. 2538      * @param Math_BigInteger $n
  2539. 2539      * @return Math_BigInteger
  2540. 2540      * @access public
  2541. 2541      * @internal Calculates the GCD using the binary xGCD algorithim described in
  2542. 2542      *    {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}.  As the text above 14.61 notes,
  2543. 2543      *    the more traditional algorithim requires "relatively costly multiple-precision divisions".
  2544. 2544      */
  2545. 2545     function extendedGCD($n)
  2546. 2546     {
  2547. 2547         switch (MATH_BIGINTEGER_MODE) {
  2548. 2548             case MATH_BIGINTEGER_MODE_GMP:
  2549. 2549                 extract(gmp_gcdext($this->value$n->value));
  2550. 2550 
  2551. 2551                 return array(
  2552. 2552                     'gcd' => $this->_normalize(new Math_BigInteger($g)),
  2553. 2553                     'x'   => $this->_normalize(new Math_BigInteger($s)),
  2554. 2554                     'y'   => $this->_normalize(new Math_BigInteger($t))
  2555. 2555                 );
  2556. 2556             case MATH_BIGINTEGER_MODE_BCMATH:
  2557. 2557                 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
  2558. 2558                 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
  2559. 2559                 // the basic extended euclidean algorithim is what we're using.
  2560. 2560 
  2561. 2561                 $u $this->value;
  2562. 2562                 $v $n->value;
  2563. 2563 
  2564. 2564                 $a '1';
  2565. 2565                 $b '0';
  2566. 2566                 $c '0';
  2567. 2567                 $d '1';
  2568. 2568 
  2569. 2569                 while (bccomp($v'0'0) != 0) {
  2570. 2570                     $q bcdiv($u$v0);
  2571. 2571 
  2572. 2572                     $temp $u;
  2573. 2573                     $u $v;
  2574. 2574                     $v bcsub($tempbcmul($v$q0), 0);
  2575. 2575 
  2576. 2576                     $temp $a;
  2577. 2577                     $a $c;
  2578. 2578                     $c bcsub($tempbcmul($a$q0), 0);
  2579. 2579 
  2580. 2580                     $temp $b;
  2581. 2581                     $b $d;
  2582. 2582                     $d bcsub($tempbcmul($b$q0), 0);
  2583. 2583                 }
  2584. 2584 
  2585. 2585                 return array(
  2586. 2586                     'gcd' => $this->_normalize(new Math_BigInteger($u)),
  2587. 2587                     'x'   => $this->_normalize(new Math_BigInteger($a)),
  2588. 2588                     'y'   => $this->_normalize(new Math_BigInteger($b))
  2589. 2589                 );
  2590. 2590         }
  2591. 2591 
  2592. 2592         $y $n->copy();
  2593. 2593         $x $this->copy();
  2594. 2594         $g = new Math_BigInteger();
  2595. 2595         $g->value = array(1);
  2596. 2596 
  2597. 2597         while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
  2598. 2598             $x->_rshift(1);
  2599. 2599             $y->_rshift(1);
  2600. 2600             $g->_lshift(1);
  2601. 2601         }
  2602. 2602 
  2603. 2603         $u $x->copy();
  2604. 2604         $v $y->copy();
  2605. 2605 
  2606. 2606         $a = new Math_BigInteger();
  2607. 2607         $b = new Math_BigInteger();
  2608. 2608         $c = new Math_BigInteger();
  2609. 2609         $d = new Math_BigInteger();
  2610. 2610 
  2611. 2611         $a->value $d->value $g->value = array(1);
  2612. 2612         $b->value $c->value = array();
  2613. 2613 
  2614. 2614         while (!empty($u->value)) {
  2615. 2615             while (!($u->value[0] & 1)) {
  2616. 2616                 $u->_rshift(1);
  2617. 2617                 if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
  2618. 2618                     $a $a->add($y);
  2619. 2619                     $b $b->subtract($x);
  2620. 2620                 }
  2621. 2621                 $a->_rshift(1);
  2622. 2622                 $b->_rshift(1);
  2623. 2623             }
  2624. 2624 
  2625. 2625             while (!($v->value[0] & 1)) {
  2626. 2626                 $v->_rshift(1);
  2627. 2627                 if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
  2628. 2628                     $c $c->add($y);
  2629. 2629                     $d $d->subtract($x);
  2630. 2630                 }
  2631. 2631                 $c->_rshift(1);
  2632. 2632                 $d->_rshift(1);
  2633. 2633             }
  2634. 2634 
  2635. 2635             if ($u->compare($v) >= 0) {
  2636. 2636                 $u $u->subtract($v);
  2637. 2637                 $a $a->subtract($c);
  2638. 2638                 $b $b->subtract($d);
  2639. 2639             } else {
  2640. 2640                 $v $v->subtract($u);
  2641. 2641                 $c $c->subtract($a);
  2642. 2642                 $d $d->subtract($b);
  2643. 2643             }
  2644. 2644         }
  2645. 2645 
  2646. 2646         return array(
  2647. 2647             'gcd' => $this->_normalize($g->multiply($v)),
  2648. 2648             'x'   => $this->_normalize($c),
  2649. 2649             'y'   => $this->_normalize($d)
  2650. 2650         );
  2651. 2651     }
  2652. 2652 
  2653. 2653     /**
  2654. 2654      * Calculates the greatest common divisor
  2655. 2655      *
  2656. 2656      * Say you have 693 and 609.  The GCD is 21.
  2657. 2657      *
  2658. 2658      * Here's an example:
  2659. 2659      * <code>
  2660. 2660      * <?php
  2661. 2661      *    include 'Math/BigInteger.php';
  2662. 2662      *
  2663. 2663      *    $a = new Math_BigInteger(693);
  2664. 2664      *    $b = new Math_BigInteger(609);
  2665. 2665      *
  2666. 2666      *    $gcd = a->extendedGCD($b);
  2667. 2667      *
  2668. 2668      *    echo $gcd->toString() . "\r\n"; // outputs 21
  2669. 2669      * ?>
  2670. 2670      * </code>
  2671. 2671      *
  2672. 2672      * @param Math_BigInteger $n
  2673. 2673      * @return Math_BigInteger
  2674. 2674      * @access public
  2675. 2675      */
  2676. 2676     function gcd($n)
  2677. 2677     {
  2678. 2678         extract($this->extendedGCD($n));
  2679. 2679         return $gcd;
  2680. 2680     }
  2681. 2681 
  2682. 2682     /**
  2683. 2683      * Absolute value.
  2684. 2684      *
  2685. 2685      * @return Math_BigInteger
  2686. 2686      * @access public
  2687. 2687      */
  2688. 2688     function abs()
  2689. 2689     {
  2690. 2690         $temp = new Math_BigInteger();
  2691. 2691 
  2692. 2692         switch (MATH_BIGINTEGER_MODE) {
  2693. 2693             case MATH_BIGINTEGER_MODE_GMP:
  2694. 2694                 $temp->value gmp_abs($this->value);
  2695. 2695                 break;
  2696. 2696             case MATH_BIGINTEGER_MODE_BCMATH:
  2697. 2697                 $temp->value = (bccomp($this->value'0'0) < 0) ? substr($this->value1) : $this->value;
  2698. 2698                 break;
  2699. 2699             default:
  2700. 2700                 $temp->value $this->value;
  2701. 2701         }
  2702. 2702 
  2703. 2703         return $temp;
  2704. 2704     }
  2705. 2705 
  2706. 2706     /**
  2707. 2707      * Compares two numbers.
  2708. 2708      *
  2709. 2709      * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
  2710. 2710      * demonstrated thusly:
  2711. 2711      *
  2712. 2712      * $x  > $y: $x->compare($y)  > 0
  2713. 2713      * $x  < $y: $x->compare($y)  < 0
  2714. 2714      * $x == $y: $x->compare($y) == 0
  2715. 2715      *
  2716. 2716      * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
  2717. 2717      *
  2718. 2718      * @param Math_BigInteger $y
  2719. 2719      * @return int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
  2720. 2720      * @access public
  2721. 2721      * @see self::equals()
  2722. 2722      * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
  2723. 2723      */
  2724. 2724     function compare($y)
  2725. 2725     {
  2726. 2726         switch (MATH_BIGINTEGER_MODE) {
  2727. 2727             case MATH_BIGINTEGER_MODE_GMP:
  2728. 2728                 return gmp_cmp($this->value$y->value);
  2729. 2729             case MATH_BIGINTEGER_MODE_BCMATH:
  2730. 2730                 return bccomp($this->value$y->value0);
  2731. 2731         }
  2732. 2732 
  2733. 2733         return $this->_compare($this->value$this->is_negative$y->value$y->is_negative);
  2734. 2734     }
  2735. 2735 
  2736. 2736     /**
  2737. 2737      * Compares two numbers.
  2738. 2738      *
  2739. 2739      * @param array $x_value
  2740. 2740      * @param bool $x_negative
  2741. 2741      * @param array $y_value
  2742. 2742      * @param bool $y_negative
  2743. 2743      * @return int
  2744. 2744      * @see self::compare()
  2745. 2745      * @access private
  2746. 2746      */
  2747. 2747     function _compare($x_value$x_negative$y_value$y_negative)
  2748. 2748     {
  2749. 2749         if ($x_negative != $y_negative) {
  2750. 2750             return (!$x_negative && $y_negative) ? : -1;
  2751. 2751         }
  2752. 2752 
  2753. 2753         $result $x_negative ? -1;
  2754. 2754 
  2755. 2755         if (count($x_value) != count($y_value)) {
  2756. 2756             return (count($x_value) > count($y_value)) ? $result : -$result;
  2757. 2757         }
  2758. 2758         $size max(count($x_value), count($y_value));
  2759. 2759 
  2760. 2760         $x_value array_pad($x_value$size0);
  2761. 2761         $y_value array_pad($y_value$size0);
  2762. 2762 
  2763. 2763         for ($i count($x_value) - 1$i >= 0; --$i) {
  2764. 2764             if ($x_value[$i] != $y_value[$i]) {
  2765. 2765                 return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
  2766. 2766             }
  2767. 2767         }
  2768. 2768 
  2769. 2769         return 0;
  2770. 2770     }
  2771. 2771 
  2772. 2772     /**
  2773. 2773      * Tests the equality of two numbers.
  2774. 2774      *
  2775. 2775      * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
  2776. 2776      *
  2777. 2777      * @param Math_BigInteger $x
  2778. 2778      * @return bool
  2779. 2779      * @access public
  2780. 2780      * @see self::compare()
  2781. 2781      */
  2782. 2782     function equals($x)
  2783. 2783     {
  2784. 2784         switch (MATH_BIGINTEGER_MODE) {
  2785. 2785             case MATH_BIGINTEGER_MODE_GMP:
  2786. 2786                 return gmp_cmp($this->value$x->value) == 0;
  2787. 2787             default:
  2788. 2788                 return $this->value === $x->value && $this->is_negative == $x->is_negative;
  2789. 2789         }
  2790. 2790     }
  2791. 2791 
  2792. 2792     /**
  2793. 2793      * Set Precision
  2794. 2794      *
  2795. 2795      * Some bitwise operations give different results depending on the precision being used.  Examples include left
  2796. 2796      * shift, not, and rotates.
  2797. 2797      *
  2798. 2798      * @param int $bits
  2799. 2799      * @access public
  2800. 2800      */
  2801. 2801     function setPrecision($bits)
  2802. 2802     {
  2803. 2803         $this->precision $bits;
  2804. 2804         if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH) {
  2805. 2805             $this->bitmask = new Math_BigInteger(chr((<< ($bits 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
  2806. 2806         } else {
  2807. 2807             $this->bitmask = new Math_BigInteger(bcpow('2'$bits0));
  2808. 2808         }
  2809. 2809 
  2810. 2810         $temp $this->_normalize($this);
  2811. 2811         $this->value $temp->value;
  2812. 2812     }
  2813. 2813 
  2814. 2814     /**
  2815. 2815      * Logical And
  2816. 2816      *
  2817. 2817      * @param Math_BigInteger $x
  2818. 2818      * @access public
  2819. 2819      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2820. 2820      * @return Math_BigInteger
  2821. 2821      */
  2822. 2822     function bitwise_and($x)
  2823. 2823     {
  2824. 2824         switch (MATH_BIGINTEGER_MODE) {
  2825. 2825             case MATH_BIGINTEGER_MODE_GMP:
  2826. 2826                 $temp = new Math_BigInteger();
  2827. 2827                 $temp->value gmp_and($this->value$x->value);
  2828. 2828 
  2829. 2829                 return $this->_normalize($temp);
  2830. 2830             case MATH_BIGINTEGER_MODE_BCMATH:
  2831. 2831                 $left $this->toBytes();
  2832. 2832                 $right $x->toBytes();
  2833. 2833 
  2834. 2834                 $length max(strlen($left), strlen($right));
  2835. 2835 
  2836. 2836                 $left str_pad($left$lengthchr(0), STR_PAD_LEFT);
  2837. 2837                 $right str_pad($right$lengthchr(0), STR_PAD_LEFT);
  2838. 2838 
  2839. 2839                 return $this->_normalize(new Math_BigInteger($left $right256));
  2840. 2840         }
  2841. 2841 
  2842. 2842         $result $this->copy();
  2843. 2843 
  2844. 2844         $length min(count($x->value), count($this->value));
  2845. 2845 
  2846. 2846         $result->value array_slice($result->value0$length);
  2847. 2847 
  2848. 2848         for ($i 0$i $length; ++$i) {
  2849. 2849             $result->value[$i]&= $x->value[$i];
  2850. 2850         }
  2851. 2851 
  2852. 2852         return $this->_normalize($result);
  2853. 2853     }
  2854. 2854 
  2855. 2855     /**
  2856. 2856      * Logical Or
  2857. 2857      *
  2858. 2858      * @param Math_BigInteger $x
  2859. 2859      * @access public
  2860. 2860      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2861. 2861      * @return Math_BigInteger
  2862. 2862      */
  2863. 2863     function bitwise_or($x)
  2864. 2864     {
  2865. 2865         switch (MATH_BIGINTEGER_MODE) {
  2866. 2866             case MATH_BIGINTEGER_MODE_GMP:
  2867. 2867                 $temp = new Math_BigInteger();
  2868. 2868                 $temp->value gmp_or($this->value$x->value);
  2869. 2869 
  2870. 2870                 return $this->_normalize($temp);
  2871. 2871             case MATH_BIGINTEGER_MODE_BCMATH:
  2872. 2872                 $left $this->toBytes();
  2873. 2873                 $right $x->toBytes();
  2874. 2874 
  2875. 2875                 $length max(strlen($left), strlen($right));
  2876. 2876 
  2877. 2877                 $left str_pad($left$lengthchr(0), STR_PAD_LEFT);
  2878. 2878                 $right str_pad($right$lengthchr(0), STR_PAD_LEFT);
  2879. 2879 
  2880. 2880                 return $this->_normalize(new Math_BigInteger($left $right256));
  2881. 2881         }
  2882. 2882 
  2883. 2883         $length max(count($this->value), count($x->value));
  2884. 2884         $result $this->copy();
  2885. 2885         $result->value array_pad($result->value$length0);
  2886. 2886         $x->value array_pad($x->value$length0);
  2887. 2887 
  2888. 2888         for ($i 0$i $length; ++$i) {
  2889. 2889             $result->value[$i]|= $x->value[$i];
  2890. 2890         }
  2891. 2891 
  2892. 2892         return $this->_normalize($result);
  2893. 2893     }
  2894. 2894 
  2895. 2895     /**
  2896. 2896      * Logical Exclusive-Or
  2897. 2897      *
  2898. 2898      * @param Math_BigInteger $x
  2899. 2899      * @access public
  2900. 2900      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2901. 2901      * @return Math_BigInteger
  2902. 2902      */
  2903. 2903     function bitwise_xor($x)
  2904. 2904     {
  2905. 2905         switch (MATH_BIGINTEGER_MODE) {
  2906. 2906             case MATH_BIGINTEGER_MODE_GMP:
  2907. 2907                 $temp = new Math_BigInteger();
  2908. 2908                 $temp->value gmp_xor(gmp_abs($this->value), gmp_abs($x->value));
  2909. 2909 
  2910. 2910                 return $this->_normalize($temp);
  2911. 2911             case MATH_BIGINTEGER_MODE_BCMATH:
  2912. 2912                 $left $this->toBytes();
  2913. 2913                 $right $x->toBytes();
  2914. 2914 
  2915. 2915                 $length max(strlen($left), strlen($right));
  2916. 2916 
  2917. 2917                 $left str_pad($left$lengthchr(0), STR_PAD_LEFT);
  2918. 2918                 $right str_pad($right$lengthchr(0), STR_PAD_LEFT);
  2919. 2919 
  2920. 2920                 return $this->_normalize(new Math_BigInteger($left $right256));
  2921. 2921         }
  2922. 2922 
  2923. 2923         $length max(count($this->value), count($x->value));
  2924. 2924         $result $this->copy();
  2925. 2925         $result->is_negative false;
  2926. 2926         $result->value array_pad($result->value$length0);
  2927. 2927         $x->value array_pad($x->value$length0);
  2928. 2928 
  2929. 2929         for ($i 0$i $length; ++$i) {
  2930. 2930             $result->value[$i]^= $x->value[$i];
  2931. 2931         }
  2932. 2932 
  2933. 2933         return $this->_normalize($result);
  2934. 2934     }
  2935. 2935 
  2936. 2936     /**
  2937. 2937      * Logical Not
  2938. 2938      *
  2939. 2939      * @access public
  2940. 2940      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2941. 2941      * @return Math_BigInteger
  2942. 2942      */
  2943. 2943     function bitwise_not()
  2944. 2944     {
  2945. 2945         // calculuate "not" without regard to $this->precision
  2946. 2946         // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)
  2947. 2947         $temp $this->toBytes();
  2948. 2948         if ($temp == '') {
  2949. 2949             return $this->_normalize(new Math_BigInteger());
  2950. 2950         }
  2951. 2951         $pre_msb decbin(ord($temp[0]));
  2952. 2952         $temp = ~$temp;
  2953. 2953         $msb decbin(ord($temp[0]));
  2954. 2954         if (strlen($msb) == 8) {
  2955. 2955             $msb substr($msbstrpos($msb'0'));
  2956. 2956         }
  2957. 2957         $temp[0] = chr(bindec($msb));
  2958. 2958 
  2959. 2959         // see if we need to add extra leading 1's
  2960. 2960         $current_bits strlen($pre_msb) + strlen($temp) - 8;
  2961. 2961         $new_bits $this->precision $current_bits;
  2962. 2962         if ($new_bits <= 0) {
  2963. 2963             return $this->_normalize(new Math_BigInteger($temp256));
  2964. 2964         }
  2965. 2965 
  2966. 2966         // generate as many leading 1's as we need to.
  2967. 2967         $leading_ones chr((<< ($new_bits 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
  2968. 2968         $this->_base256_lshift($leading_ones$current_bits);
  2969. 2969 
  2970. 2970         $temp str_pad($tempstrlen($leading_ones), chr(0), STR_PAD_LEFT);
  2971. 2971 
  2972. 2972         return $this->_normalize(new Math_BigInteger($leading_ones $temp256));
  2973. 2973     }
  2974. 2974 
  2975. 2975     /**
  2976. 2976      * Logical Right Shift
  2977. 2977      *
  2978. 2978      * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
  2979. 2979      *
  2980. 2980      * @param int $shift
  2981. 2981      * @return Math_BigInteger
  2982. 2982      * @access public
  2983. 2983      * @internal The only version that yields any speed increases is the internal version.
  2984. 2984      */
  2985. 2985     function bitwise_rightShift($shift)
  2986. 2986     {
  2987. 2987         $temp = new Math_BigInteger();
  2988. 2988 
  2989. 2989         switch (MATH_BIGINTEGER_MODE) {
  2990. 2990             case MATH_BIGINTEGER_MODE_GMP:
  2991. 2991                 static $two;
  2992. 2992 
  2993. 2993                 if (!isset($two)) {
  2994. 2994                     $two gmp_init('2');
  2995. 2995                 }
  2996. 2996 
  2997. 2997                 $temp->value gmp_div_q($this->valuegmp_pow($two$shift));
  2998. 2998 
  2999. 2999                 break;
  3000. 3000             case MATH_BIGINTEGER_MODE_BCMATH:
  3001. 3001                 $temp->value bcdiv($this->valuebcpow('2'$shift0), 0);
  3002. 3002 
  3003. 3003                 break;
  3004. 3004             default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
  3005. 3005                      // and I don't want to do that...
  3006. 3006                 $temp->value $this->value;
  3007. 3007                 $temp->_rshift($shift);
  3008. 3008         }
  3009. 3009 
  3010. 3010         return $this->_normalize($temp);
  3011. 3011     }
  3012. 3012 
  3013. 3013     /**
  3014. 3014      * Logical Left Shift
  3015. 3015      *
  3016. 3016      * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
  3017. 3017      *
  3018. 3018      * @param int $shift
  3019. 3019      * @return Math_BigInteger
  3020. 3020      * @access public
  3021. 3021      * @internal The only version that yields any speed increases is the internal version.
  3022. 3022      */
  3023. 3023     function bitwise_leftShift($shift)
  3024. 3024     {
  3025. 3025         $temp = new Math_BigInteger();
  3026. 3026 
  3027. 3027         switch (MATH_BIGINTEGER_MODE) {
  3028. 3028             case MATH_BIGINTEGER_MODE_GMP:
  3029. 3029                 static $two;
  3030. 3030 
  3031. 3031                 if (!isset($two)) {
  3032. 3032                     $two gmp_init('2');
  3033. 3033                 }
  3034. 3034 
  3035. 3035                 $temp->value gmp_mul($this->valuegmp_pow($two$shift));
  3036. 3036 
  3037. 3037                 break;
  3038. 3038             case MATH_BIGINTEGER_MODE_BCMATH:
  3039. 3039                 $temp->value bcmul($this->valuebcpow('2'$shift0), 0);
  3040. 3040 
  3041. 3041                 break;
  3042. 3042             default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
  3043. 3043                      // and I don't want to do that...
  3044. 3044                 $temp->value $this->value;
  3045. 3045                 $temp->_lshift($shift);
  3046. 3046         }
  3047. 3047 
  3048. 3048         return $this->_normalize($temp);
  3049. 3049     }
  3050. 3050 
  3051. 3051     /**
  3052. 3052      * Logical Left Rotate
  3053. 3053      *
  3054. 3054      * Instead of the top x bits being dropped they're appended to the shifted bit string.
  3055. 3055      *
  3056. 3056      * @param int $shift
  3057. 3057      * @return Math_BigInteger
  3058. 3058      * @access public
  3059. 3059      */
  3060. 3060     function bitwise_leftRotate($shift)
  3061. 3061     {
  3062. 3062         $bits $this->toBytes();
  3063. 3063 
  3064. 3064         if ($this->precision 0) {
  3065. 3065             $precision $this->precision;
  3066. 3066             if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
  3067. 3067                 $mask $this->bitmask->subtract(new Math_BigInteger(1));
  3068. 3068                 $mask $mask->toBytes();
  3069. 3069             } else {
  3070. 3070                 $mask $this->bitmask->toBytes();
  3071. 3071             }
  3072. 3072         } else {
  3073. 3073             $temp ord($bits[0]);
  3074. 3074             for ($i 0$temp >> $i; ++$i) {
  3075. 3075             }
  3076. 3076             $precision strlen($bits) - $i;
  3077. 3077             $mask chr((<< ($precision 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
  3078. 3078         }
  3079. 3079 
  3080. 3080         if ($shift 0) {
  3081. 3081             $shift+= $precision;
  3082. 3082         }
  3083. 3083         $shift%= $precision;
  3084. 3084 
  3085. 3085         if (!$shift) {
  3086. 3086             return $this->copy();
  3087. 3087         }
  3088. 3088 
  3089. 3089         $left $this->bitwise_leftShift($shift);
  3090. 3090         $left $left->bitwise_and(new Math_BigInteger($mask256));
  3091. 3091         $right $this->bitwise_rightShift($precision $shift);
  3092. 3092         $result MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH $left->bitwise_or($right) : $left->add($right);
  3093. 3093         return $this->_normalize($result);
  3094. 3094     }
  3095. 3095 
  3096. 3096     /**
  3097. 3097      * Logical Right Rotate
  3098. 3098      *
  3099. 3099      * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
  3100. 3100      *
  3101. 3101      * @param int $shift
  3102. 3102      * @return Math_BigInteger
  3103. 3103      * @access public
  3104. 3104      */
  3105. 3105     function bitwise_rightRotate($shift)
  3106. 3106     {
  3107. 3107         return $this->bitwise_leftRotate(-$shift);
  3108. 3108     }
  3109. 3109 
  3110. 3110     /**
  3111. 3111      * Set random number generator function
  3112. 3112      *
  3113. 3113      * This function is deprecated.
  3114. 3114      *
  3115. 3115      * @param string $generator
  3116. 3116      * @access public
  3117. 3117      */
  3118. 3118     function setRandomGenerator($generator)
  3119. 3119     {
  3120. 3120     }
  3121. 3121 
  3122. 3122     /**
  3123. 3123      * Generates a random BigInteger
  3124. 3124      *
  3125. 3125      * Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not.
  3126. 3126      *
  3127. 3127      * @param int $length
  3128. 3128      * @return Math_BigInteger
  3129. 3129      * @access private
  3130. 3130      */
  3131. 3131     function _random_number_helper($size)
  3132. 3132     {
  3133. 3133         if (function_exists('crypt_random_string')) {
  3134. 3134             $random crypt_random_string($size);
  3135. 3135         } else {
  3136. 3136             $random '';
  3137. 3137 
  3138. 3138             if ($size 1) {
  3139. 3139                 $random.= chr(mt_rand(0255));
  3140. 3140             }
  3141. 3141 
  3142. 3142             $blocks $size >> 1;
  3143. 3143             for ($i 0$i $blocks; ++$i) {
  3144. 3144                 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
  3145. 3145                 $random.= pack('n'mt_rand(00xFFFF));
  3146. 3146             }
  3147. 3147         }
  3148. 3148 
  3149. 3149         return new Math_BigInteger($random256);
  3150. 3150     }
  3151. 3151 
  3152. 3152     /**
  3153. 3153      * Generate a random number
  3154. 3154      *
  3155. 3155      * Returns a random number between $min and $max where $min and $max
  3156. 3156      * can be defined using one of the two methods:
  3157. 3157      *
  3158. 3158      * $min->random($max)
  3159. 3159      * $max->random($min)
  3160. 3160      *
  3161. 3161      * @param Math_BigInteger $arg1
  3162. 3162      * @param Math_BigInteger $arg2
  3163. 3163      * @return Math_BigInteger
  3164. 3164      * @access public
  3165. 3165      * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a Math_BigInteger object.
  3166. 3166      *           That method is still supported for BC purposes.
  3167. 3167      */
  3168. 3168     function random($arg1$arg2 false)
  3169. 3169     {
  3170. 3170         if ($arg1 === false) {
  3171. 3171             return false;
  3172. 3172         }
  3173. 3173 
  3174. 3174         if ($arg2 === false) {
  3175. 3175             $max $arg1;
  3176. 3176             $min $this;
  3177. 3177         } else {
  3178. 3178             $min $arg1;
  3179. 3179             $max $arg2;
  3180. 3180         }
  3181. 3181 
  3182. 3182         $compare $max->compare($min);
  3183. 3183 
  3184. 3184         if (!$compare) {
  3185. 3185             return $this->_normalize($min);
  3186. 3186         } elseif ($compare 0) {
  3187. 3187             // if $min is bigger then $max, swap $min and $max
  3188. 3188             $temp $max;
  3189. 3189             $max $min;
  3190. 3190             $min $temp;
  3191. 3191         }
  3192. 3192 
  3193. 3193         static $one;
  3194. 3194         if (!isset($one)) {
  3195. 3195             $one = new Math_BigInteger(1);
  3196. 3196         }
  3197. 3197 
  3198. 3198         $max $max->subtract($min->subtract($one));
  3199. 3199         $size strlen(ltrim($max->toBytes(), chr(0)));
  3200. 3200 
  3201. 3201         /*
  3202. 3202             doing $random % $max doesn't work because some numbers will be more likely to occur than others.
  3203. 3203             eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
  3204. 3204             would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
  3205. 3205             not all numbers would be equally likely. some would be more likely than others.
  3206. 3206 
  3207. 3207             creating a whole new random number until you find one that is within the range doesn't work
  3208. 3208             because, for sufficiently small ranges, the likelihood that you'd get a number within that range
  3209. 3209             would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
  3210. 3210             would be pretty high that $random would be greater than $max.
  3211. 3211 
  3212. 3212             phpseclib works around this using the technique described here:
  3213. 3213 
  3214. 3214             http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
  3215. 3215         */
  3216. 3216         $random_max = new Math_BigInteger(chr(1) . str_repeat("\0"$size), 256);
  3217. 3217         $random $this->_random_number_helper($size);
  3218. 3218 
  3219. 3219         list($max_multiple) = $random_max->divide($max);
  3220. 3220         $max_multiple $max_multiple->multiply($max);
  3221. 3221 
  3222. 3222         while ($random->compare($max_multiple) >= 0) {
  3223. 3223             $random $random->subtract($max_multiple);
  3224. 3224             $random_max $random_max->subtract($max_multiple);
  3225. 3225             $random $random->bitwise_leftShift(8);
  3226. 3226             $random $random->add($this->_random_number_helper(1));
  3227. 3227             $random_max $random_max->bitwise_leftShift(8);
  3228. 3228             list($max_multiple) = $random_max->divide($max);
  3229. 3229             $max_multiple $max_multiple->multiply($max);
  3230. 3230         }
  3231. 3231         list(, $random) = $random->divide($max);
  3232. 3232 
  3233. 3233         return $this->_normalize($random->add($min));
  3234. 3234     }
  3235. 3235 
  3236. 3236     /**
  3237. 3237      * Generate a random prime number.
  3238. 3238      *
  3239. 3239      * If there's not a prime within the given range, false will be returned.
  3240. 3240      * If more than $timeout seconds have elapsed, give up and return false.
  3241. 3241      *
  3242. 3242      * @param Math_BigInteger $arg1
  3243. 3243      * @param Math_BigInteger $arg2
  3244. 3244      * @param int $timeout
  3245. 3245      * @return Math_BigInteger|false
  3246. 3246      * @access public
  3247. 3247      * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
  3248. 3248      */
  3249. 3249     function randomPrime($arg1$arg2 false$timeout false)
  3250. 3250     {
  3251. 3251         if ($arg1 === false) {
  3252. 3252             return false;
  3253. 3253         }
  3254. 3254 
  3255. 3255         if ($arg2 === false) {
  3256. 3256             $max $arg1;
  3257. 3257             $min $this;
  3258. 3258         } else {
  3259. 3259             $min $arg1;
  3260. 3260             $max $arg2;
  3261. 3261         }
  3262. 3262 
  3263. 3263         $compare $max->compare($min);
  3264. 3264 
  3265. 3265         if (!$compare) {
  3266. 3266             return $min->isPrime() ? $min false;
  3267. 3267         } elseif ($compare 0) {
  3268. 3268             // if $min is bigger then $max, swap $min and $max
  3269. 3269             $temp $max;
  3270. 3270             $max $min;
  3271. 3271             $min $temp;
  3272. 3272         }
  3273. 3273 
  3274. 3274         static $one$two;
  3275. 3275         if (!isset($one)) {
  3276. 3276             $one = new Math_BigInteger(1);
  3277. 3277             $two = new Math_BigInteger(2);
  3278. 3278         }
  3279. 3279 
  3280. 3280         $start time();
  3281. 3281 
  3282. 3282         $x $this->random($min$max);
  3283. 3283 
  3284. 3284         // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
  3285. 3285         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && extension_loaded('gmp') && version_compare(PHP_VERSION'5.2.0''>=')) {
  3286. 3286             $p = new Math_BigInteger();
  3287. 3287             $p->value gmp_nextprime($x->value);
  3288. 3288 
  3289. 3289             if ($p->compare($max) <= 0) {
  3290. 3290                 return $p;
  3291. 3291             }
  3292. 3292 
  3293. 3293             if (!$min->equals($x)) {
  3294. 3294                 $x $x->subtract($one);
  3295. 3295             }
  3296. 3296 
  3297. 3297             return $x->randomPrime($min$x);
  3298. 3298         }
  3299. 3299 
  3300. 3300         if ($x->equals($two)) {
  3301. 3301             return $x;
  3302. 3302         }
  3303. 3303 
  3304. 3304         $x->_make_odd();
  3305. 3305         if ($x->compare($max) > 0) {
  3306. 3306             // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
  3307. 3307             if ($min->equals($max)) {
  3308. 3308                 return false;
  3309. 3309             }
  3310. 3310             $x $min->copy();
  3311. 3311             $x->_make_odd();
  3312. 3312         }
  3313. 3313 
  3314. 3314         $initial_x $x->copy();
  3315. 3315 
  3316. 3316         while (true) {
  3317. 3317             if ($timeout !== false && time() - $start $timeout) {
  3318. 3318                 return false;
  3319. 3319             }
  3320. 3320 
  3321. 3321             if ($x->isPrime()) {
  3322. 3322                 return $x;
  3323. 3323             }
  3324. 3324 
  3325. 3325             $x $x->add($two);
  3326. 3326 
  3327. 3327             if ($x->compare($max) > 0) {
  3328. 3328                 $x $min->copy();
  3329. 3329                 if ($x->equals($two)) {
  3330. 3330                     return $x;
  3331. 3331                 }
  3332. 3332                 $x->_make_odd();
  3333. 3333             }
  3334. 3334 
  3335. 3335             if ($x->equals($initial_x)) {
  3336. 3336                 return false;
  3337. 3337             }
  3338. 3338         }
  3339. 3339     }
  3340. 3340 
  3341. 3341     /**
  3342. 3342      * Make the current number odd
  3343. 3343      *
  3344. 3344      * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
  3345. 3345      *
  3346. 3346      * @see self::randomPrime()
  3347. 3347      * @access private
  3348. 3348      */
  3349. 3349     function _make_odd()
  3350. 3350     {
  3351. 3351         switch (MATH_BIGINTEGER_MODE) {
  3352. 3352             case MATH_BIGINTEGER_MODE_GMP:
  3353. 3353                 gmp_setbit($this->value0);
  3354. 3354                 break;
  3355. 3355             case MATH_BIGINTEGER_MODE_BCMATH:
  3356. 3356                 if ($this->value[strlen($this->value) - 1] % == 0) {
  3357. 3357                     $this->value bcadd($this->value'1');
  3358. 3358                 }
  3359. 3359                 break;
  3360. 3360             default:
  3361. 3361                 $this->value[0] |= 1;
  3362. 3362         }
  3363. 3363     }
  3364. 3364 
  3365. 3365     /**
  3366. 3366      * Checks a numer to see if it's prime
  3367. 3367      *
  3368. 3368      * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
  3369. 3369      * $t parameter is distributability.  Math_BigInteger::randomPrime() can be distributed across multiple pageloads
  3370. 3370      * on a website instead of just one.
  3371. 3371      *
  3372. 3372      * @param Math_BigInteger $t
  3373. 3373      * @return bool
  3374. 3374      * @access public
  3375. 3375      * @internal Uses the
  3376. 3376      *     {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}.  See
  3377. 3377      *     {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
  3378. 3378      */
  3379. 3379     function isPrime($t false)
  3380. 3380     {
  3381. 3381         $length strlen($this->toBytes());
  3382. 3382 
  3383. 3383         if (!$t) {
  3384. 3384             // see HAC 4.49 "Note (controlling the error probability)"
  3385. 3385             // @codingStandardsIgnoreStart
  3386. 3386                  if ($length >= 163) { $t =  2; } // floor(1300 / 8)
  3387. 3387             else if ($length >= 106) { $t =  3; } // floor( 850 / 8)
  3388. 3388             else if ($length >= 81 ) { $t =  4; } // floor( 650 / 8)
  3389. 3389             else if ($length >= 68 ) { $t =  5; } // floor( 550 / 8)
  3390. 3390             else if ($length >= 56 ) { $t =  6; } // floor( 450 / 8)
  3391. 3391             else if ($length >= 50 ) { $t =  7; } // floor( 400 / 8)
  3392. 3392             else if ($length >= 43 ) { $t =  8; } // floor( 350 / 8)
  3393. 3393             else if ($length >= 37 ) { $t =  9; } // floor( 300 / 8)
  3394. 3394             else if ($length >= 31 ) { $t 12; } // floor( 250 / 8)
  3395. 3395             else if ($length >= 25 ) { $t 15; } // floor( 200 / 8)
  3396. 3396             else if ($length >= 18 ) { $t 18; } // floor( 150 / 8)
  3397. 3397             else                     { $t 27; }
  3398. 3398             // @codingStandardsIgnoreEnd
  3399. 3399         }
  3400. 3400 
  3401. 3401         // ie. gmp_testbit($this, 0)
  3402. 3402         // ie. isEven() or !isOdd()
  3403. 3403         switch (MATH_BIGINTEGER_MODE) {
  3404. 3404             case MATH_BIGINTEGER_MODE_GMP:
  3405. 3405                 return gmp_prob_prime($this->value$t) != 0;
  3406. 3406             case MATH_BIGINTEGER_MODE_BCMATH:
  3407. 3407                 if ($this->value === '2') {
  3408. 3408                     return true;
  3409. 3409                 }
  3410. 3410                 if ($this->value[strlen($this->value) - 1] % == 0) {
  3411. 3411                     return false;
  3412. 3412                 }
  3413. 3413                 break;
  3414. 3414             default:
  3415. 3415                 if ($this->value == array(2)) {
  3416. 3416                     return true;
  3417. 3417                 }
  3418. 3418                 if (~$this->value[0] & 1) {
  3419. 3419                     return false;
  3420. 3420                 }
  3421. 3421         }
  3422. 3422 
  3423. 3423         static $primes$zero$one$two;
  3424. 3424 
  3425. 3425         if (!isset($primes)) {
  3426. 3426             $primes = array(
  3427. 3427                 3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,
  3428. 3428                 61,   67,   71,   73,   79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,
  3429. 3429                 139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,  227,
  3430. 3430                 229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,  313,
  3431. 3431                 317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
  3432. 3432                 421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,
  3433. 3433                 521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,
  3434. 3434                 619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
  3435. 3435                 733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,  829,
  3436. 3436                 839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
  3437. 3437                 953,  967,  971,  977,  983,  991,  997
  3438. 3438             );
  3439. 3439 
  3440. 3440             if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
  3441. 3441                 for ($i 0$i count($primes); ++$i) {
  3442. 3442                     $primes[$i] = new Math_BigInteger($primes[$i]);
  3443. 3443                 }
  3444. 3444             }
  3445. 3445 
  3446. 3446             $zero = new Math_BigInteger();
  3447. 3447             $one = new Math_BigInteger(1);
  3448. 3448             $two = new Math_BigInteger(2);
  3449. 3449         }
  3450. 3450 
  3451. 3451         if ($this->equals($one)) {
  3452. 3452             return false;
  3453. 3453         }
  3454. 3454 
  3455. 3455         // see HAC 4.4.1 "Random search for probable primes"
  3456. 3456         if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
  3457. 3457             foreach ($primes as $prime) {
  3458. 3458                 list(, $r) = $this->divide($prime);
  3459. 3459                 if ($r->equals($zero)) {
  3460. 3460                     return $this->equals($prime);
  3461. 3461                 }
  3462. 3462             }
  3463. 3463         } else {
  3464. 3464             $value $this->value;
  3465. 3465             foreach ($primes as $prime) {
  3466. 3466                 list(, $r) = $this->_divide_digit($value$prime);
  3467. 3467                 if (!$r) {
  3468. 3468                     return count($value) == && $value[0] == $prime;
  3469. 3469                 }
  3470. 3470             }
  3471. 3471         }
  3472. 3472 
  3473. 3473         $n   $this->copy();
  3474. 3474         $n_1 $n->subtract($one);
  3475. 3475         $n_2 $n->subtract($two);
  3476. 3476 
  3477. 3477         $r $n_1->copy();
  3478. 3478         $r_value $r->value;
  3479. 3479         // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
  3480. 3480         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
  3481. 3481             $s 0;
  3482. 3482             // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
  3483. 3483             while ($r->value[strlen($r->value) - 1] % == 0) {
  3484. 3484                 $r->value bcdiv($r->value'2'0);
  3485. 3485                 ++$s;
  3486. 3486             }
  3487. 3487         } else {
  3488. 3488             for ($i 0$r_length count($r_value); $i $r_length; ++$i) {
  3489. 3489                 $temp = ~$r_value[$i] & 0xFFFFFF;
  3490. 3490                 for ($j 1; ($temp >> $j) & 1; ++$j) {
  3491. 3491                 }
  3492. 3492                 if ($j != 25) {
  3493. 3493                     break;
  3494. 3494                 }
  3495. 3495             }
  3496. 3496             $s 26 $i $j;
  3497. 3497             $r->_rshift($s);
  3498. 3498         }
  3499. 3499 
  3500. 3500         for ($i 0$i $t; ++$i) {
  3501. 3501             $a $this->random($two$n_2);
  3502. 3502             $y $a->modPow($r$n);
  3503. 3503 
  3504. 3504             if (!$y->equals($one) && !$y->equals($n_1)) {
  3505. 3505                 for ($j 1$j $s && !$y->equals($n_1); ++$j) {
  3506. 3506                     $y $y->modPow($two$n);
  3507. 3507                     if ($y->equals($one)) {
  3508. 3508                         return false;
  3509. 3509                     }
  3510. 3510                 }
  3511. 3511 
  3512. 3512                 if (!$y->equals($n_1)) {
  3513. 3513                     return false;
  3514. 3514                 }
  3515. 3515             }
  3516. 3516         }
  3517. 3517         return true;
  3518. 3518     }
  3519. 3519 
  3520. 3520     /**
  3521. 3521      * Logical Left Shift
  3522. 3522      *
  3523. 3523      * Shifts BigInteger's by $shift bits.
  3524. 3524      *
  3525. 3525      * @param int $shift
  3526. 3526      * @access private
  3527. 3527      */
  3528. 3528     function _lshift($shift)
  3529. 3529     {
  3530. 3530         if ($shift == 0) {
  3531. 3531             return;
  3532. 3532         }
  3533. 3533 
  3534. 3534         $num_digits = (int) ($shift MATH_BIGINTEGER_BASE);
  3535. 3535         $shift %= MATH_BIGINTEGER_BASE;
  3536. 3536         $shift << $shift;
  3537. 3537 
  3538. 3538         $carry 0;
  3539. 3539 
  3540. 3540         for ($i 0$i count($this->value); ++$i) {
  3541. 3541             $temp $this->value[$i] * $shift $carry;
  3542. 3542             $carry MATH_BIGINTEGER_BASE === 26 intval($temp 0x4000000) : ($temp >> 31);
  3543. 3543             $this->value[$i] = (int) ($temp $carry MATH_BIGINTEGER_BASE_FULL);
  3544. 3544         }
  3545. 3545 
  3546. 3546         if ($carry) {
  3547. 3547             $this->value[count($this->value)] = $carry;
  3548. 3548         }
  3549. 3549 
  3550. 3550         while ($num_digits--) {
  3551. 3551             array_unshift($this->value0);
  3552. 3552         }
  3553. 3553     }
  3554. 3554 
  3555. 3555     /**
  3556. 3556      * Logical Right Shift
  3557. 3557      *
  3558. 3558      * Shifts BigInteger's by $shift bits.
  3559. 3559      *
  3560. 3560      * @param int $shift
  3561. 3561      * @access private
  3562. 3562      */
  3563. 3563     function _rshift($shift)
  3564. 3564     {
  3565. 3565         if ($shift == 0) {
  3566. 3566             return;
  3567. 3567         }
  3568. 3568 
  3569. 3569         $num_digits = (int) ($shift MATH_BIGINTEGER_BASE);
  3570. 3570         $shift %= MATH_BIGINTEGER_BASE;
  3571. 3571         $carry_shift MATH_BIGINTEGER_BASE $shift;
  3572. 3572         $carry_mask = (<< $shift) - 1;
  3573. 3573 
  3574. 3574         if ($num_digits) {
  3575. 3575             $this->value array_slice($this->value$num_digits);
  3576. 3576         }
  3577. 3577 
  3578. 3578         $carry 0;
  3579. 3579 
  3580. 3580         for ($i count($this->value) - 1$i >= 0; --$i) {
  3581. 3581             $temp $this->value[$i] >> $shift $carry;
  3582. 3582             $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
  3583. 3583             $this->value[$i] = $temp;
  3584. 3584         }
  3585. 3585 
  3586. 3586         $this->value $this->_trim($this->value);
  3587. 3587     }
  3588. 3588 
  3589. 3589     /**
  3590. 3590      * Normalize
  3591. 3591      *
  3592. 3592      * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
  3593. 3593      *
  3594. 3594      * @param Math_BigInteger
  3595. 3595      * @return Math_BigInteger
  3596. 3596      * @see self::_trim()
  3597. 3597      * @access private
  3598. 3598      */
  3599. 3599     function _normalize($result)
  3600. 3600     {
  3601. 3601         $result->precision $this->precision;
  3602. 3602         $result->bitmask $this->bitmask;
  3603. 3603 
  3604. 3604         switch (MATH_BIGINTEGER_MODE) {
  3605. 3605             case MATH_BIGINTEGER_MODE_GMP:
  3606. 3606                 if ($this->bitmask !== false) {
  3607. 3607                     $result->value gmp_and($result->value$result->bitmask->value);
  3608. 3608                 }
  3609. 3609 
  3610. 3610                 return $result;
  3611. 3611             case MATH_BIGINTEGER_MODE_BCMATH:
  3612. 3612                 if (!empty($result->bitmask->value)) {
  3613. 3613                     $result->value bcmod($result->value$result->bitmask->value);
  3614. 3614                 }
  3615. 3615 
  3616. 3616                 return $result;
  3617. 3617         }
  3618. 3618 
  3619. 3619         $value = &$result->value;
  3620. 3620 
  3621. 3621         if (!count($value)) {
  3622. 3622             return $result;
  3623. 3623         }
  3624. 3624 
  3625. 3625         $value $this->_trim($value);
  3626. 3626 
  3627. 3627         if (!empty($result->bitmask->value)) {
  3628. 3628             $length min(count($value), count($this->bitmask->value));
  3629. 3629             $value array_slice($value0$length);
  3630. 3630 
  3631. 3631             for ($i 0$i $length; ++$i) {
  3632. 3632                 $value[$i] = $value[$i] & $this->bitmask->value[$i];
  3633. 3633             }
  3634. 3634         }
  3635. 3635 
  3636. 3636         return $result;
  3637. 3637     }
  3638. 3638 
  3639. 3639     /**
  3640. 3640      * Trim
  3641. 3641      *
  3642. 3642      * Removes leading zeros
  3643. 3643      *
  3644. 3644      * @param array $value
  3645. 3645      * @return Math_BigInteger
  3646. 3646      * @access private
  3647. 3647      */
  3648. 3648     function _trim($value)
  3649. 3649     {
  3650. 3650         for ($i count($value) - 1$i >= 0; --$i) {
  3651. 3651             if ($value[$i]) {
  3652. 3652                 break;
  3653. 3653             }
  3654. 3654             unset($value[$i]);
  3655. 3655         }
  3656. 3656 
  3657. 3657         return $value;
  3658. 3658     }
  3659. 3659 
  3660. 3660     /**
  3661. 3661      * Array Repeat
  3662. 3662      *
  3663. 3663      * @param $input Array
  3664. 3664      * @param $multiplier mixed
  3665. 3665      * @return array
  3666. 3666      * @access private
  3667. 3667      */
  3668. 3668     function _array_repeat($input$multiplier)
  3669. 3669     {
  3670. 3670         return ($multiplier) ? array_fill(0$multiplier$input) : array();
  3671. 3671     }
  3672. 3672 
  3673. 3673     /**
  3674. 3674      * Logical Left Shift
  3675. 3675      *
  3676. 3676      * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
  3677. 3677      *
  3678. 3678      * @param $x String
  3679. 3679      * @param $shift Integer
  3680. 3680      * @return string
  3681. 3681      * @access private
  3682. 3682      */
  3683. 3683     function _base256_lshift(&$x$shift)
  3684. 3684     {
  3685. 3685         if ($shift == 0) {
  3686. 3686             return;
  3687. 3687         }
  3688. 3688 
  3689. 3689         $num_bytes $shift >> 3// eg. floor($shift/8)
  3690. 3690         $shift &= 7// eg. $shift % 8
  3691. 3691 
  3692. 3692         $carry 0;
  3693. 3693         for ($i strlen($x) - 1$i >= 0; --$i) {
  3694. 3694             $temp ord($x[$i]) << $shift $carry;
  3695. 3695             $x[$i] = chr($temp);
  3696. 3696             $carry $temp >> 8;
  3697. 3697         }
  3698. 3698         $carry = ($carry != 0) ? chr($carry) : '';
  3699. 3699         $x $carry $x str_repeat(chr(0), $num_bytes);
  3700. 3700     }
  3701. 3701 
  3702. 3702     /**
  3703. 3703      * Logical Right Shift
  3704. 3704      *
  3705. 3705      * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
  3706. 3706      *
  3707. 3707      * @param $x String
  3708. 3708      * @param $shift Integer
  3709. 3709      * @return string
  3710. 3710      * @access private
  3711. 3711      */
  3712. 3712     function _base256_rshift(&$x$shift)
  3713. 3713     {
  3714. 3714         if ($shift == 0) {
  3715. 3715             $x ltrim($xchr(0));
  3716. 3716             return '';
  3717. 3717         }
  3718. 3718 
  3719. 3719         $num_bytes $shift >> 3// eg. floor($shift/8)
  3720. 3720         $shift &= 7// eg. $shift % 8
  3721. 3721 
  3722. 3722         $remainder '';
  3723. 3723         if ($num_bytes) {
  3724. 3724             $start $num_bytes strlen($x) ? -strlen($x) : -$num_bytes;
  3725. 3725             $remainder substr($x$start);
  3726. 3726             $x substr($x0, -$num_bytes);
  3727. 3727         }
  3728. 3728 
  3729. 3729         $carry 0;
  3730. 3730         $carry_shift $shift;
  3731. 3731         for ($i 0$i strlen($x); ++$i) {
  3732. 3732             $temp = (ord($x[$i]) >> $shift) | $carry;
  3733. 3733             $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
  3734. 3734             $x[$i] = chr($temp);
  3735. 3735         }
  3736. 3736         $x ltrim($xchr(0));
  3737. 3737 
  3738. 3738         $remainder chr($carry >> $carry_shift) . $remainder;
  3739. 3739 
  3740. 3740         return ltrim($remainderchr(0));
  3741. 3741     }
  3742. 3742 
  3743. 3743     // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
  3744. 3744     // at 32-bits, while java's longs are 64-bits.
  3745. 3745 
  3746. 3746     /**
  3747. 3747      * Converts 32-bit integers to bytes.
  3748. 3748      *
  3749. 3749      * @param int $x
  3750. 3750      * @return string
  3751. 3751      * @access private
  3752. 3752      */
  3753. 3753     function _int2bytes($x)
  3754. 3754     {
  3755. 3755         return ltrim(pack('N'$x), chr(0));
  3756. 3756     }
  3757. 3757 
  3758. 3758     /**
  3759. 3759      * Converts bytes to 32-bit integers
  3760. 3760      *
  3761. 3761      * @param string $x
  3762. 3762      * @return int
  3763. 3763      * @access private
  3764. 3764      */
  3765. 3765     function _bytes2int($x)
  3766. 3766     {
  3767. 3767         $temp unpack('Nint'str_pad($x4chr(0), STR_PAD_LEFT));
  3768. 3768         return $temp['int'];
  3769. 3769     }
  3770. 3770 
  3771. 3771     /**
  3772. 3772      * DER-encode an integer
  3773. 3773      *
  3774. 3774      * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
  3775. 3775      *
  3776. 3776      * @see self::modPow()
  3777. 3777      * @access private
  3778. 3778      * @param int $length
  3779. 3779      * @return string
  3780. 3780      */
  3781. 3781     function _encodeASN1Length($length)
  3782. 3782     {
  3783. 3783         if ($length <= 0x7F) {
  3784. 3784             return chr($length);
  3785. 3785         }
  3786. 3786 
  3787. 3787         $temp ltrim(pack('N'$length), chr(0));
  3788. 3788         return pack('Ca*'0x80 strlen($temp), $temp);
  3789. 3789     }
  3790. 3790 
  3791. 3791     /**
  3792. 3792      * Single digit division
  3793. 3793      *
  3794. 3794      * Even if int64 is being used the division operator will return a float64 value
  3795. 3795      * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
  3796. 3796      * have the precision of int64 this is a problem so, when int64 is being used,
  3797. 3797      * we'll guarantee that the dividend is divisible by first subtracting the remainder.
  3798. 3798      *
  3799. 3799      * @access private
  3800. 3800      * @param int $x
  3801. 3801      * @param int $y
  3802. 3802      * @return int
  3803. 3803      */
  3804. 3804     function _safe_divide($x$y)
  3805. 3805     {
  3806. 3806         if (MATH_BIGINTEGER_BASE === 26) {
  3807. 3807             return (int) ($x $y);
  3808. 3808         }
  3809. 3809 
  3810. 3810         // MATH_BIGINTEGER_BASE === 31
  3811. 3811         return ($x - ($x $y)) / $y;
  3812. 3812     }
  3813. 3813 }